Mastering Algorithms - Binary Search

What is Binary Search?

Binary Search is an efficient search algorithm that finds the position of a target value within a sorted array. The algorithm works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The key requirement for binary search is that the data structure must be sorted. This allows the algorithm to eliminate half of the remaining elements at each step, making it significantly faster than linear search for large datasets. Binary search can be implemented both iteratively and recursively, with the iterative approach generally being preferred for its better space efficiency.

Binary search has a time complexity of O(log n), where n is the number of elements in the array. This logarithmic time complexity makes it extremely efficient for large datasets. The space complexity is O(1) for the iterative implementation and O(log n) for the recursive implementation due to the call stack. Binary search is one of the most fundamental algorithms in computer science and forms the basis for many advanced search techniques.

Beyond simple search, binary search can be adapted for various problems including finding insertion points, searching in rotated arrays, finding boundaries, and solving optimization problems where we need to find the minimum or maximum value satisfying certain conditions. It's also used in data structures like binary search trees and is fundamental to many divide-and-conquer algorithms.

Binary Search Algorithm Pseudocode

            
            BinarySearch(arr, target):
                left = 0
                right = arr.length - 1
                
                while left <= right:
                    mid = left + (right - left) // 2
                    
                    if arr[mid] == target:
                        return mid
                    elif arr[mid] < target:
                        left = mid + 1
                    else:
                        right = mid - 1
                
                return -1  # Target not found

Common Trends in Problems where Binary Search is Applied

Sorted Arrays: Binary search requires sorted data, making it perfect for problems involving sorted arrays or when you can sort the data first.
Search Space Reduction: Problems where you need to eliminate half the search space at each step naturally fit binary search.
Boundary Finding: Binary search excels at finding boundaries, such as the first or last occurrence of an element, or insertion points.
Optimization Problems: When searching for a minimum or maximum value that satisfies certain conditions, binary search on the answer space is often the solution.
Monotonic Functions: Problems involving monotonic functions (always increasing or decreasing) can often be solved using binary search.

Binary Search Framework

Initialize left and right pointers to define the search space (typically 0 and n-1 for arrays).
Use a while loop that continues while left <= right (or left < right depending on the problem).
Calculate the middle index using left + (right - left) // 2 to avoid integer overflow.
Compare the middle element with the target and adjust the search space accordingly.
Handle edge cases carefully, especially when the target is not found or when dealing with duplicate values.

Popular LeetCode Questions Using Binary Search

704. Binary Search

Problem:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Solution:

This is the classic binary search problem. Since the array is sorted, we can use binary search to find the target in O(log n) time. We maintain two pointers, left and right, that define the current search space. At each step, we calculate the middle index and compare the element at that position with the target. If they match, we return the index. If the middle element is less than the target, we search the right half. Otherwise, we search the left half.

The key is to correctly update the boundaries: if arr[mid] < target, we set left = mid + 1 (since mid is already checked and too small). If arr[mid] > target, we set right = mid - 1. The loop continues until left > right, at which point the target is not in the array. The time complexity is O(log n) and the space complexity is O(1).

                
                    class Solution:
                        def search(self, nums: List[int], target: int) -> int:
                            left, right = 0, len(nums) - 1
                            
                            while left <= right:
                                mid = left + (right - left) // 2
                                
                                if nums[mid] == target:
                                    return mid
                                elif nums[mid] < target:
                                    left = mid + 1
                                else:
                                    right = mid - 1
                            
                            return -1