The Binary Search algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.


Binary Search is a searching algorithm for finding an element's position in a sorted array. 

In this approach, the element is always searched in the middle of a portion of an array.

Binary search can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.


Binary Search Working:


1. The array in which searching is to be performed is: [3, 4, 5, 6, 7, 8, 9]

Let x = 4 be the element to be searched.


2. Set two pointers low and high at the lowest and the highest positions respectively.


3. Find the middle element mid of the array i.e. arr[(low + high)/2] = 6.

4. If x == mid, then return mid. Else, compare the element to be searched with m.


5.  If x > mid, compare x with the middle element of the elements on the right side of mid. This is done by setting low to low = mid + 1.


6. Else, compare x with the middle element of the elements on the left side of mid. This is done by setting high to high = mid - 1.



7. Repeat steps 3 to 6 until low meets high.


8. x = 4 is found.




Let's start with the algorithm,


var binarySearch = function(sortedArray, key){

    let start = 0;

    let end = sortedArray.length - 1;


    while (start <= end) {

        let middle = Math.floor((start + end) / 2);


        if (sortedArray[middle] === key) {

            // found the key

            return middle;

        } else if (sortedArray[middle] < key) {

            // continue searching to the right

            start = middle + 1;

        } else {

            // search searching to the left

            end = middle - 1;

        }

    }

  // key wasn't found

    return -1;

}



Time Complexities:

  • Best case complexity: O(1)
  • Average case complexity: O(log n)
  • Worst case complexity: O(log n)


I hope you understood the algorithm. If you have any doubts, please let us know in the comments.