1
/*
2
* binary-search.test.ts
3
*
4
* Copyright (C) 2021-2022 Posit Software, PBC
5
*
6
*/
7

8
import { glb } from "../../src/core/lib/binary-search.ts";
9
import bounds from "binary-search-bounds";
10

11
import { unitTest } from "../test.ts";
12
import { assert } from "testing/asserts";
13

14
// deno-lint-ignore require-await
15
unitTest("binary-search-test - glb property tests", async () => {
16
  // test by randomization that glb() behaves like le()
17

18
  const nTests = 1000;
19
  // const nTests = 10000000; // this passed locally
20
  for (let i = 0; i < nTests; ++i) {
21
    const sz = ~~(Math.random() * 10);
22
    const a: number[] = [];
23
    for (let j = 0; j < sz; ++j) {
24
      a.push(~~(Math.random() * 10));
25
    }
26
    a.sort();
27
    const n = ~~(Math.random() * 10);
28
    const ours = glb(a, n);
29
    const theirs = bounds.le(a, n);
30
    if (ours !== theirs) {
31
      console.log("randomization failed!", { a, n });
32
    }
33
    assert(ours === theirs);
34
  }
35
});
36

37
// deno-lint-ignore require-await
38
unitTest("binary-search-test - previous failures", async () => {
39
  assert(glb([1, 2, 4, 5, 5, 6, 6, 7, 7], 9) === 8);
40
  assert(glb([5, 8, 9], 1) === -1);
41
  assert(glb([5], 4) === -1);
42
  assert(glb([5], 5) === 0);
43
  assert(glb([5], 6) === 0);
44
});
45

46