-
-
Notifications
You must be signed in to change notification settings - Fork 156
/
binarySearch.js
66 lines (57 loc) · 1.25 KB
/
binarySearch.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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/* Binary search implementation.
*
* |Name |Desc |
* |------|-------------|
* |array |Sorted array |
* |val |Value to seek|
* |cmp |Comparator |
* |return|Value index |
*/
/* example
* binarySearch([1, 2, 3], 2); // -> 1
* binarySearch([1, 2], 3); // -> -1
* binarySearch(
* [
* {
* key: 1
* },
* {
* key: 2
* }
* ],
* { key: 1 },
* (a, b) => {
* if (a.key === b.key) return 0;
* return a.key < b.key ? -1 : 1;
* }
* ); // -> 0
*/
/* module
* env: all
* since: 1.4.0
*/
/* typescript
* export declare function binarySearch(
* array: any[],
* val: any,
* cmp?: types.AnyFn
* ): number;
*/
_('isSorted types');
exports = function(arr, val, cmp = isSorted.defComparator) {
let startIdx = 0;
let endIdx = arr.length - 1;
while (startIdx <= endIdx) {
const middleIdx = startIdx + Math.floor((endIdx - startIdx) / 2);
const middleVal = arr[middleIdx];
if (cmp(middleVal, val) === 0) {
return middleIdx;
}
if (cmp(middleVal, val) < 0) {
startIdx = middleIdx + 1;
} else {
endIdx = middleIdx - 1;
}
}
return -1;
};