Data Structures and Algorithms - Binary Search

The Binary Search algorithm is a search algorithm to find a specific element in an array. Binary search only works on sorted arrays. Binary search works by eliminating half of the elements every time you look for the desired element. The halving continuses until you find the elements or find it does not exist in the array. The time complexity is O(logN) which is fast compared to Linear search O(N).

Pseudocode

1. Set a lower bound (left) to 0
2. Set an upper bound (right) to the last element of the array ( array.length - 1 )
3. While the lower bound is less than or equal to the upper bound we will do the following:
   1. Create a midpoint variable, ( upper bound - lower bound ) / 2
   2. If the midpoint variable is less than the element we are searching for, set a new lower bound: midpoint + 1
   3. If the midpoint variable is greater than the element we are searching for, set a new lower bound: midpoint - 1
   4. If the element we are looking for equals an element in the array at the index of the midpoint (num === arr[mid]) return the midpoint variable
   5. if the element we are looking for does not exist in the array return -1

Code

function binarySearch(arr, num){
  let left = 0,
      right = arr.length -1;

      while(left <= right) {
        let mid = Math.floor((left + right) /2);//using Math.floor() handles decimals
        //console.log('left:', left, 'right:', right, 'mid:', mid);
        if(num === arr[mid]) {
            return mid;
        }

        if (num > arr[mid]){
          left = mid +1;
        }

        if (num < arr[mid]){
          right = mid -1;
        }
      }
  return -1;
}

//binarySearch([1,2,3,4,5,6,7,8,9], 9)
//left: 0 right: 8 mid: 4
//left: 5 right: 8 mid: 6
//left: 7 right: 8 mid: 7
//left: 8 right: 8 mid: 8
//arr[mid] 9, num= 9

If you want to track the left, right and mid variables and see how binary search divides the array uncomment the console.log in the code.