-
Notifications
You must be signed in to change notification settings - Fork 7
/
binsearch.js
48 lines (48 loc) · 1.66 KB
/
binsearch.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"use strict";
exports.__esModule = true;
function binsearch_helper(arr, start, end, v, comparator) {
// console.log("binsearch_helper: " + start + ", " + end + ", comparing against " + v);
if (start >= end) {
return -1; // not found
}
var midpoint = Math.floor((start + end) / 2);
// console.log("midpoint = " + midpoint);
// Find the earliest matching index.
var comparison = comparator(arr[midpoint], v);
// if ((arr[midpoint] === v) && ((midpoint === 0) || (arr[midpoint-1] != v))) {
if (comparison === 0) {
// console.log("A");
// Found it. Is it the earliest one?
if ((midpoint === 0) || (comparator(arr[midpoint - 1], v) != 0)) {
return midpoint;
}
}
if (comparison < 0) {
// console.log("B");
return binsearch_helper(arr, midpoint + 1, end, v, comparator);
}
else {
// console.log("C");
return binsearch_helper(arr, start, midpoint - 1, v, comparator);
}
}
// Find the index of the earliest occurrence of v in arr using binary search.
// Return -1 if not found.
function binsearch(arr, v, comparator) {
if (comparator === void 0) { comparator = undefined; }
if (typeof comparator === "undefined") {
// console.log("undefined");
comparator = (function (a, b) {
console.log("Comparing " + JSON.stringify(a) + " to " + JSON.stringify(b));
if (a === b) {
return 0;
}
if (a < b) {
return -1;
}
return 1;
});
}
return binsearch_helper(arr, 0, arr.length, v, comparator);
}
exports.binsearch = binsearch;