Binary search technique is used to search for any element in a sorted array using divide and conquer approach.
/**
* Binary Search
* Note - It works only for the sorted array. start and end are left and right of the array.
*
* Recursive Approach
* - If starting index is greater than the ending index return false
* - Compute the middle index.
* - Compare the middle element with the number x. If equal return true.
* - If greater, call the same function with ending index = middle-1 and repeat step 1.
* - If smaller, call the same function with starting index = middle+1 and repeat step 1.
*
* Time Complexity: O(logN)
* Auxiliary Space: O(1)
*/
const arr = [1, 3, 5, 7, 8, 9];
const binarySearchRecursive = (arr, val, start, end) => {
if (start > end) return false;
const mid = Math.floor((start + end) / 2);
if (arr[mid] === val) return mid;
const left = arr[mid] > val ? start : mid + 1;
const right = arr[mid] > val ? mid - 1 : end;
return binarySearchRecursive(arr, val, left, right);
}
console.log(binarySearchRecursive(arr, 5, 0, arr.length - 1)); // -> 2
Top comments (0)