Coding Patterns - Binary search

Intuition

Binary search is more than just finding an element in a sorted array. Its core principle is repeatedly dividing a search space in half and can be extended to a wide variety of problems. By leveraging binary search on answers, monotonic properties, or rotated arrays, we can solve problems that seem unrelated to searching.

Think of binary search as playing a guessing game: if someone thinks of a number between 1 and 100, you don’t check sequentially, you halve the range each time until you find it.

Binary Search Strategies

1. Standard Binary Search

• Find target in a sorted array.

• Time complexity: O(log n).

2. Binary Search on Condition

• Use when the answer lies in a monotonic function (true/false boundary).

• Example: Minimum capacity to ship packages in D days.

3. Search in Rotated Sorted Array

• Adjust search by checking which half is sorted.

4. Binary Search on Answer Space

• Instead of searching in the input, search in the range of possible answers.

• Example: Find minimum days to complete tasks, square root calculation, etc.

When To Use Binary Search

Use binary search when:

• Input is sorted or can be transformed into a monotonic space.

• The problem asks for optimization (min/max value satisfying condition).

• You need logarithmic performance on large inputs.

Real-World Example

Bandwidth Allocation: ISPs use binary search-like optimization to allocate bandwidth fairly. By testing capacities and checking feasibility (too high/low), they converge on an optimal threshold.

Manufacturing: Finding the minimum time to produce a certain number of items given machine speeds can be solved with binary search on time.

Coding Example 1: Standard Binary Search

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example usage
print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3

Coding Example 2: Find Minimum in Rotated Sorted Array

def find_min_rotated(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

# Example usage
print(find_min_rotated([4,5,6,7,0,1,2]))  # 0

Framework

1. Check Preconditions: Ensure sorted or monotonic property exists.

2. Define Search Space: Indices of array or possible range of answers.

3. Calculate Midpoint: (left + right) // 2.

4. Shrink Range: Move left or right based on condition.

5. Return Answer: Index or boundary depending on problem.

Key Points

• Binary search works on arrays and abstract answer spaces.

• Rotated arrays and condition-based problems are extensions.

• Optimizations reduce complexity from linear to logarithmic.

• Powerful tool for interview-style optimization problems.

Practice Exercise

Exercise: Implement a function to find the square root of a number using binary search (without using math libraries).

Sample Solution:

def sqrt_binary_search(x):
    if x < 2:
        return x
    left, right = 1, x // 2
    while left <= right:
        mid = (left + right) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
            ans = mid
        else:
            right = mid - 1
    return ans

# Example usage
print(sqrt_binary_search(16))  # 4
print(sqrt_binary_search(20))  # 4

Next Chapter