blob: bc281ca0dad71f7a8f9df7befe39b14ad0f9e707 (
plain)
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
|
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) {
// The naive `low + high >>> 1` could fail for array lengths > 2**31
// because `>>>` converts its operands to int32. `low + (high - low >>> 1)`
// works for array lengths <= 2**32-1 which is also Javascript's max array
// length.
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;
}
|
