Binary Search

This is a search algorithm where you take an array identify it's middle value, then update the upper and lower bounds of the search and loop again until the target value is found.

2, 3, 4, 10, 40 -> 3
2, 3, 4 -> 3 == array[1]

Binary Search - Time:O(log N), Space O(1)

  This is looping through an array in halfs and measuring the middle index until you've found the index of the item you're looking for.

  Here you start with understanding the overall boundaries of the array, 0 to (length-1). Then begin to loop through the array so long as the low index is less than the high index.

  In each loop you find the mid index by adding the low index to the floor(rounded down value) of (high-low)/2. Next check the mid index's value to see if it's the target value. If it is return that mid value index as the answer. If the number is higher then the high index need to be lowered to the position just lower than this one. If it's lower than the low index needs to be updated to 1 position high than the mid index. If nothing is found after all loops, then return -1.

function binarySearch(arr, x) {
    let low = 0;
    let high = arr.length - 1;
    let mid;
    while (high >= low) {
        mid = low + Math.floor((high - low) / 2);

        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            high = mid - 1;

        // Else the element can only be present
        // in right subarray
        else
            low = mid + 1;
    }

    // We reach here when element is not
    // present in array
    return -1;
}

// Driver Code
arr = new Array(2, 3, 4, 10, 40);
x = 10;
result = binarySearch(arr, x);
if (result == -1)
    console.log("Element is not present in array")
    else
    console.log("Element is present at index "
                    + result);

---

Recursive Binary Search - Time:O(log N), Space O(log N)

  The recursive binary search operates very similary to the normal binary search, however it recursively calls itself to loop instead of utilizing a while loop.

// A recursive binary search function. It returns
// location of x in given array arr[low..high] is present,
// otherwise -1
function binarySearch(arr, low, high, x) {
    if (high >= low) {
        let mid = low + Math.floor((high - low) / 2);

        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, low, mid - 1, x);

        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, high, x);
    }

    // We reach here when element is not
    // present in array
    return -1;
}

// Driver Code
let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let n = arr.length
let result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
    console.log("Element is not present in array");
else
    console.log("Element is present at index " + result);