Binary Search

Binary search is an efficient algorithm for finding a specific target value within a sorted array. It significantly reduces the number of comparisons needed compared to a linear scan, making it crucial for performance in large datasets.

How Binary Search Works

Binary search operates by repeatedly dividing the search interval in half. It leverages the sorted nature of the array to quickly narrow down the potential location of the target.

First, initialize two pointers: `l` at the beginning of the array (index 0) and `r` at the end of the array (index `len(nums) - 1`). These pointers define the current search space.

Next, enter a loop that continues as long as `l` is less than or equal to `r`. Inside the loop, calculate the middle index `mid` using `(l + r) // 2`. Compare the value at `nums[mid]` with the `target`:

• If `nums[mid]` equals `target`, the target is found, and its index `mid` is returned.
• If `nums[mid]` is less than `target`, it means the target, if present, must be in the right half of the current search space. Update `l` to `mid + 1` to discard the left half.
• If `nums[mid]` is greater than `target`, the target, if present, must be in the left half. Update `r` to `mid - 1` to discard the right half.

If the loop finishes without finding the target (i.e., `l` becomes greater than `r`), it means the target is not present in the array, and typically -1 is returned.

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

Key Takeaways

• Binary search requires the input array to be sorted.
• It works by repeatedly halving the search interval.
• Pointers `l` and `r` define the current boundaries of the search.
• The middle element `nums[mid]` is compared to the target to decide which half to continue searching.
• It offers logarithmic time complexity (O(log n)), making it very efficient for large arrays.