1const arr = [1, 3, 5, 7, 8, 9];
2const binarySearch = (arr, x , start=0, end=arr.length) => {
3 // If the item does not exist, return -1
4 if(end < start) return -1;
5
6 // Calculate middle index of the array
7 let mid = Math.floor((start + end) / 2);
8
9 // Is the middle a match?
10 if(arr[mid] === x) return mid;
11 // Is the middle less than x
12 if(arr[mid] < x) return binarySearch(arr, x, mid+1, end);
13 // Else the middle is more than x
14 else return binarySearch(arr, x , start, mid-1);
15}
16
17binarySearch(arr, 7); // Returns 3
18/* O(n) of binarySearch is log(n) */
1function binarySearch(arr, val) {
2 let start = 0;
3 let end = arr.length - 1;
4
5 while (start <= end) {
6 let mid = Math.floor((start + end) / 2);
7
8 if (arr[mid] === val) {
9 return mid;
10 }
11
12 if (val < arr[mid]) {
13 end = mid - 1;
14 } else {
15 start = mid + 1;
16 }
17 }
18 return -1;
19}
20
1function binarySearchIndex (array, target, low = 0, high = array.length - 1) {
2 if (low > high) {
3 return -1
4 }
5 const midPoint = Math.floor((low + high) / 2)
6
7 if (target < array[midPoint]) {
8 return binarySearchIndex(array, target, low, midPoint - 1)
9 } else if (target > array[midPoint]) {
10 return binarySearchIndex(array, target, midPoint + 1, high)
11 } else {
12 return midPoint
13 }
14}