Binary Search

#beginners #programming #tutorial #algorithms

What is Binary Search?

A binary search is an algorithm used to find the position of a specific value in a sorted array. The algorithm repeatedly divides the search interval in half until the value is found or the search interval becomes empty.

Example of a Binary Search function in Javascript:

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

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

The binarySearch function takes two arguments: the array to be searched (arr) and the target value to be found (target). It initializes two pointers, left and right, to the beginning and end of the array, respectively.

The function then enters a while loop that continues as long as left is less than or equal to right. In each iteration, the function calculates the midpoint index (mid) of the search interval using the formula (left + right) / 2. It then compares the value at the midpoint with the target value.

If the midpoint value is equal to the target value, the function returns the midpoint index. If the midpoint value is less than the target value, the function updates left to mid + 1, effectively discarding the left half of the search interval. If the midpoint value is greater than the target value, the function updates right to mid - 1, effectively discarding the right half of the search interval.

If the function completes the while loop without finding the target value, it returns -1 to indicate that the value was not found in the array.

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

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 7;

const index = binarySearch(arr, target);
console.log(index); // Output: 6

When to use Binary Search?

Binary search is a very efficient algorithm for searching in a sorted array or list. It has a time complexity of O(log n), which is much faster than linear search (which has a time complexity of O(n)).

Binary search is particularly useful when searching through very large datasets or when search performance is critical. It is commonly used in applications such as search engines, databases, and scientific computing.

Binary search is most effective when:

The data is sorted: Binary search requires the data to be sorted in order for the algorithm to work correctly. If the data is not sorted, the algorithm may not find the correct answer.
The data is static or nearly static: If the data is constantly changing, binary search may not be the best algorithm to use. Each time the data changes, the sorting process must be repeated, which can be very time-consuming.
The data size is large: Binary search is most effective when the data set is large. If the data set is small, the overhead of sorting the data and implementing the algorithm may not be worth the performance benefits.

In summary, binary search is a powerful algorithm that can provide significant performance improvements in the right situations. If you need to search through a large dataset that is static or nearly static and sorted, binary search is a great option to consider.