/**
 * 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