-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathstructy-116-binarySearch.js
65 lines (54 loc) · 1.6 KB
/
structy-116-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
// p: arr & num
// r: +num/-1
const binarySearch = (nums, target) => {
let s = 0,
e = nums.length - 1;
while (s <= e) {
let m = Math.floor((s + e) / 2);
if (nums[m] === target) return m;
nums[m] < target ? (s = m + 1) : (e = m - 1);
}
return -1;
};
// // better:
// const binarySearch = (numbers, target) => {
// let lo = 0;
// let hi = numbers.length - 1;
// while (lo <= hi) {
// const mid = Math.floor((lo + hi) / 2);
// if (numbers[mid] === target) {
// return mid;
// } else if (target < numbers[mid]) {
// hi = mid - 1;
// } else {
// lo = mid + 1;
// }
// }
// return -1;
// };
// const binarySearch = (numbers, target) => {
// // 0 1 2 3
// // 0 1 2 3 4
// let start = 0;
// let end = numbers.length - 1;
// let midI = findMidI(start, end);
// while (start < end) {
// // console.log(start, midI, end);
// if (target === numbers[midI]) {
// return midI;
// } else if (target < numbers[midI]) {
// end = midI - 1;
// midI = findMidI(start, end);
// } else {
// start = midI + 1;
// midI = findMidI(start, end);
// }
// }
// if (numbers[start] === target) return start;
// if (numbers[end] === target) return end;
// return -1;
// };
// const findMidI = (s, e) => Math.floor((s + e) / 2);
// console.log(binarySearch([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 6)); // -> 6
console.log(binarySearch([0, 6, 8, 12, 16, 19, 20, 24, 28], 27)); // -> -1
// console.log(binarySearch([0, 6, 8, 12, 16, 19, 20, 24, 28], 28)); // -> 8