Binary Search

Binary Search

Welcome to Binary Search, a highly efficient algorithm for finding an item from a sorted collection. By repeatedly dividing the search interval in half, binary search can quickly narrow down the location of a target value.

---

1. The Core Idea: Divide and Conquer

Binary search embodies the "Divide and Conquer" strategy. It works by comparing the target value to the middle element of the sorted collection.

• If the target value matches the middle element, its position is found.
• If the target value is less than the middle element, the search continues in the lower half of the collection.
• If the target value is greater than the middle element, the search continues in the upper half of the collection.

This process is repeated, with the search interval being halved at each step, until the target value is found or the interval is empty.

---

2. The Algorithm Step-by-Step

1. Initialization:

   • Set two pointers, low and high, to the beginning and end of the collection, respectively.

2. Search Loop:

   • While low is less than or equal to high:
     • Calculate the mid index: mid = low + floor((high - low) / 2).
     • Compare the element at the mid index with the target value.
     • If array[mid] is equal to the target, the search is successful, and mid is returned.
     • If array[mid] is less than the target, it means the target must be in the upper half, so we update low = mid + 1.
     • If array[mid] is greater than the target, it means the target must be in the lower half, so we update high = mid - 1.

3. Target Not Found:

   • If the loop finishes without finding the target, a special value (like -1) is returned.

---

3. Implementation

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

  while (low <= high) {
    // Calculate the middle index to avoid potential overflow
    const mid = low + Math.floor((high - low) / 2);

    const midValue = sortedArray[mid];

    if (midValue === target) {
      return mid; // Target found
    } else if (midValue < target) {
      // Continue in the upper half
      low = mid + 1;
    } else {
      // Continue in the lower half
      high = mid - 1;
    }
  }

  return -1; // Target not found
}

---

4. Complexity Analysis

• Time Complexity: O(log N), where N is the number of elements. This is because the search interval is halved at each step.
• Space Complexity: O(1) for the iterative implementation.

---

5. Lower Bound and Upper Bound

Binary search can be adapted to solve more complex problems, such as finding the first or last occurrence of an element in a list with duplicates.

• Lower Bound: Finds the index of the first element that is greater than or equal to the target.
• Upper Bound: Finds the index of the first element that is strictly greater than the target.

These variations are crucial for solving problems involving range queries or frequency counts in sorted arrays.

---

Key Takeaway: Binary search is a logarithmic time searching algorithm that is extremely efficient but requires the collection to be sorted. Its divide-and-conquer approach makes it a fundamental algorithm in computer science.