What is Binary Search?

Binary search is an efficient algorithm to find the position of a target value within a sorted array or list. It operates by dividing the search interval in half repeatedly:

Compare the target value to the middle element.
If the target matches the middle element, return its index.
If the target is smaller, search the left half of the array.
If the target is larger, search the right half of the array.
Repeat until the target is found or the search interval is empty.

Key Characteristics:

Requires a sorted array.
Time complexity: \(O(\log n)\).
Space complexity: \(O(1)\) for iterative implementation and \(O(\log n)\) for recursive implementation.

How to Apply Binary Search

Steps:

Determine the Search Interval: Identify the sorted array or range to search in.
Set the Pointers:
- Initialize two pointers: left (start of the array) and right (end of the array).
Iterate or Recur:
- Calculate the middle index: \[ \text{mid} = \text{left} + \frac{\text{right} - \text{left}}{2} \]
- Compare the middle element with the target.
- Update the pointers (left or right) to narrow the search interval.
Exit Condition:
- If left > right, the target does not exist.
- Otherwise, return the index of the target.

Pseudocode

Iterative Implementation:

def binary_search(array, target):
    left = 0
    right = len(array) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # Target not found

Recurrsive Implementation

def binary_search(array, target, left, right):
    if left > right:
        return -1  # Target not found
    
    mid = left + (right - left) // 2
    if array[mid] == target:
        return mid
    elif array[mid] < target:
        return binary_search(array, target, mid + 1, right)
    else:
        return binary_search(array, target, left, mid - 1)

Common Questions

1. Why is mid calculated like that?

In binary search, the formula for calculating the middle index is:

\[ \text{mid} = \text{left} + \frac{\text{right} - \text{left}}{2} \]

This formula is designed to avoid integer overflow in programming languages where integers have a fixed range, such as C++ and Java. Here’s a detailed explanation:

Explanation

\[ \text{mid} = \frac{\text{left} + \text{right}}{2} \]
While this formula is simple and works in many cases, it has a potential issue: if left and right are very large integers, their sum (left + right) can exceed the maximum integer value, causing integer overflow.
\[ \text{mid} = \text{left} + \frac{\text{right} - \text{left}}{2} \]
This calculates the middle index without directly adding left and right.
- The term \((\text{right} - \text{left})\) represents the distance between left and right, which is much smaller than their sum.
- Dividing this distance by 2 gives the offset from left to the midpoint.
- Adding this offset back to left ensures the calculation remains within safe bounds.