Understanding Binary Search

Binary search is a powerful algorithm used to efficiently find the position of a target value within a sorted array or list. Its effectiveness lies in its ability to eliminate half of the remaining elements in each step, resulting in a logarithmic time complexity of O(log n), where n is the number of elements in the array.

Let’s break down how binary search works and provide a practical example in JavaScript.

How Binary Search Works

1 – Initial Setup:

• Start with a sorted array.
• Set two pointers, low and high, to the first and last indices of the array.

2 – Middle Element:

• Find the middle element of the array: mid = Math.floor((low + high) / 2).

3 – Comparison:

• Compare the middle element with the target value.

4 – Three Possible Cases:

• If the middle element is equal to the target value, the search is successful.
• If the middle element is greater than the target, update high to mid - 1 and search in the left half.
• If the middle element is less than the target, update low to mid + 1 and search in the right half.

5 – Repeat:

• Repeat steps 2-4 until the target value is found or low exceeds high.

6 – Termination:

• If low is greater than high, the target value is not in the array.

Example in JavaScript

Let’s implement a binary search algorithm in JavaScript:

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

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

    if (arr[mid] === target) {
      return mid; // Target found, return the index
    } else if (arr[mid] > target) {
      high = mid - 1; // Search in the left half
    } else {
      low = mid + 1; // Search in the right half
    }
  }

  return -1; // Target not found
}

// Example usage:
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const targetValue = 7;

const result = binarySearch(sortedArray, targetValue);

if (result !== -1) {
  console.log(`Target ${targetValue} found at index ${result}.`);
} else {
  console.log(`Target ${targetValue} not found in the array.`);
}

In this example, we use a binarySearch function to find the index of a target value in a sorted array. The function returns the index if the target is found and -1 otherwise.

Feel free to use this binary search algorithm in your projects when dealing with sorted data. Its efficiency makes it a valuable tool, especially for large datasets. Happy coding!