Mastering Binary Search: A Must-Know Algorithm for Any Programmer!

What is Linear Search Algorithm?

Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half.

Here’s an example implementation of binary search in JavaScript:

function binarySearch(array, target) {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

Here, the function binarySearch takes two arguments: array, which is the sorted array to search, and target, which is the value to search for. The function starts by initializing two variables: low is set to the index of the first element in the array, and high is set to the index of the last element in the array.

The function then enters a loop, which continues as long as low is less than or equal to high. On each iteration of the loop, the function calculates the midpoint of the current search interval by taking the average of low and high. If the value at the midpoint is equal to the target, the function returns the index of the midpoint.

If the value at the midpoint is less than the target, the function updates low to be mid + 1, indicating that the target must be in the upper half of the search interval. If the value at the midpoint is greater than the target, the function updates high to be mid - 1, indicating that the target must be in the lower half of the search interval.

If the target is not found in the array, the function returns -1 to indicate that the target is not present.

Here’s an example of how to use the binarySearch function:

const myArray = [1, 3, 5, 7, 9];
const index = binarySearch(myArray, 5);
console.log(index); // Output: 2

In this example, the binarySearch function is used to find the index of the value 5 in the myArray array. The function returns 2, which is the index of the value 5 in the array.