What is Binary Search ?

Binary Search is searching technique which works on Divide and Conquer approach. It used to search any element in a sorted array.

As compared to linear, binary search is much faster with Time Complexity of O(logN) whereas linear search algorithm works in O(N) time complexity.

Binary Search Step-By-Step Process Breakdown:

In this step-by-step process, we’re going to be breaking down how to do a Binary Search on the below given array.”

 const binarySearchArray = [1, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 82, 100, 101]

Target to find: 59

We are going to need to keep track of the 3 following things as variables to perform a Binary Search: startIndexPosition, middleIndexPosition, and endIndexPosition.
startIndexPosition will always be 0: let stastartIndexPositionrtIndex = 0
endIndexPosition can be calculated using array.length
We want to get an inital middleIndexPosition using the startIndexPosition and endIndexPosition, and the divide by 2. We can use Math.floor() to round down or Math.ceil() to round up.
We will use while loop in order to iterate the process
If the middleIndexPosition value is less than the target value of 59, we know that our target value will be somewhere to the right of the middleIndexPosition. We can then assign our startIndexPosition variable as the current middleIndexPosition value, ignoring the left half of the array. We should also increment middleIndexPosition by the count of 1 if our target number “59” > middleIndexPosition “31.”
If the middleIndexPosition value is greater than the target value, 59, we know that our target value will be in to the left of the middleIndexPosition. We can then assign our endIndex variable as the current middleIndex value, ignoring the right half of the array. We should also Decrement middleIndexPosition by the count of 1 if our target number “59” < middleIndexPosition “31.”
If the middleIndexPosition value is equal to the target value of 59, we have found our target number “59.”, target is found :)
Hurray we got it done

Binary Search Code:


const binarySearch = (array, target) => {
  // Define Start and End Index
  let startIndexPosition = 0;
  let endIndexPosition = array.length - 1;

  // While Start Index is less than or equal to End Index
  while(startIndexPosition <= endIndexPosition) {

    // Define Middle Index, this will keep changing 
    let middleIndexPosition = Math.floor((startIndexPosition + endIndexPosition) / 2);

    // Compare Middle Index with Target number
    if(target === array[middleIndexPosition]) {
      return console.log("Found the target" + middleIndexPosition);
    }

    // Search Right Side Of Array
    if(target > array[middleIndexPosition]) {
      console.log("Searching the right side of Array")
      // Assign Start Index and increase the Index by 1 to narrow search
      startIndexPosition = middleIndexPosition + 1;
    }

    // Search Left Side Of Array
    if(target < array[middleIndexPosition]) {
      // Assign End Index and increase the Index by 1 to narrow search
      console.log("Searching the left side of array")
      endIndexPosition = middleIndexPosition - 1;
    }
  }

  // If Target Is Not Found
  console.log("Not found sorry");
}