Binary Search

Binary search is an efficient algorithm for finding a specific target value within a sorted array. It works by repeatedly dividing the search interval in half, drastically reducing the number of comparisons needed compared to a linear scan.

How Binary Search Works

Initialization

We begin by defining two pointers: `left` and `right`. The `left` pointer is initialized to the first index of the array (0), and the `right` pointer is set to the last index (`len(nums) - 1`). These pointers define the current search interval.

Iterative Search

The core of binary search is a `while` loop that continues as long as `left` is less than or equal to `right`. Inside this loop:

1. Calculate Midpoint: A `mid` index is calculated as the integer average of `left` and `right`: `mid = (left + right) // 2`. 2. Compare and Adjust:

• If the value at `nums[mid]` is equal to the `target`, the search is successful, and `mid` is returned.
• If `nums[mid]` is less than the `target`, it means the target (if present) must be in the right half of the current interval. We update `left = mid + 1` to narrow the search to the right segment.
• If `nums[mid]` is greater than the `target`, the target (if present) must be in the left half. We update `right = mid - 1` to narrow the search to the left segment.

Termination

If the loop completes without finding the target, it means `left` has become greater than `right`, indicating that the target is not present in the array. In this case, the algorithm typically returns -1.

function binary_search(nums, target):
    left = 0
    right = length(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Key Takeaways

• Binary search requires the input array to be sorted.
• It operates by repeatedly halving the search space.
• The `left` and `right` pointers define the current search interval.
• The `mid` index is used to compare the middle element with the target.
• Its logarithmic time complexity (O(log n)) makes it highly efficient for large datasets.