forked from darkskyapp/binary-search
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.js
43 lines (34 loc) · 906 Bytes
/
index.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
module.exports = function(haystack, needle, comparator, low, high) {
var mid, cmp;
if(low === undefined)
low = 0;
else {
low = low|0;
if(low < 0 || low >= haystack.length)
throw new RangeError("invalid lower bound");
}
if(high === undefined)
high = haystack.length - 1;
else {
high = high|0;
if(high < low || high >= haystack.length)
throw new RangeError("invalid upper bound");
}
while(low <= high) {
/* Note that "(low + high) >>> 1" may overflow, and results in a typecast
* to double (which gives the wrong results). */
mid = low + (high - low >> 1);
cmp = +comparator(haystack[mid], needle, mid, haystack);
/* Too low. */
if(cmp < 0.0)
low = mid + 1;
/* Too high. */
else if(cmp > 0.0)
high = mid - 1;
/* Key found. */
else
return mid;
}
/* Key not found. */
return ~low;
}