LeetCode (5): Binary Search
Chen Kai BOSS
  2023-06-15 00:00:00 2023-06-15 00:00      12.9k Words  80 Mins  

Binary search is one of the most fundamental and powerful algorithms in computer science. Despite its apparent simplicity, mastering binary search requires understanding subtle boundary conditions, recognizing when to apply it, and knowing which template to use for different problem types. This algorithm appears in countless real-world systems, from database indexing to version control systems, and mastering it is essential for any serious programmer. This article provides a comprehensive guide to binary search, covering everything from basic concepts to advanced applications in LeetCode problems, along with practical insights into how this elegant algorithm powers modern computing systems.

Introduction

Binary search is a divide-and-conquer algorithm that efficiently locates a target value in a sorted array by repeatedly dividing the search space in half. The key insight is that if we compare the target with the middle element, we can eliminate half of the remaining elements in each iteration.

The algorithm's elegance lies in its logarithmic time complexity: while linear search takes time, binary search achievestime, making it indispensable for large datasets. To put this in perspective, searching through a billion elements requires only about 30 comparisons with binary search, compared to potentially a billion comparisons with linear search. This dramatic efficiency improvement makes binary search the algorithm of choice for search engines, databases, and any system dealing with large sorted datasets. However, the devil is in the details — off-by-one errors, boundary handling, and choosing the right template can make or break your solution. Many programmers struggle with these nuances, which is why understanding the underlying principles and practicing with various templates is crucial for mastery.

Fundamentals

Core Concept

Binary search works on the principle of elimination: at each step, we compare the target with the middle element and eliminate half of the search space.

Visualization: 

1
2
3
4
5
6
7
Initial array: [1, 3, 5, 7, 9, 11, 13, 15]
Target: 7

Step 1: Compare with middle (index 3, value 7)
        [1, 3, 5, 7, 9, 11, 13, 15]
                 ↑
        7 == 7 → Found!

Key Requirements: 1. Sorted array: The array must be sorted (ascending or descending) 2. Comparable elements: Elements must support comparison operations 3. Random access: We needaccess to any element by index

Time and Space Complexity

Time Complexity:

  • Best case: - target is at the middle
  • Average case: - typical search
  • Worst case: - target at the end or not present

Space Complexity:

  • Iterative: - only a few variables
  • Recursive: - recursion stack depth

Why?

Each iteration eliminates half the elements. Starting withelements:

  • After 1 iteration:elements remain
  • After 2 iterations:elements remain
  • Afteriterations:elements remain

We stop when, which gives us. Therefore, we need at mostiterations.

Basic Binary Search Template

The most straightforward binary search finds an exact match in a sorted array.

Standard Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(nums, target):
    """
    Standard binary search for exact match.
    Returns index if found, -1 otherwise.
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Key Points: 1. Loop condition: left <= right ensures we check all valid positions 2. Mid calculation: left + (right - left) // 2 prevents integer overflow 3. Boundary updates: mid + 1 and mid - 1 exclude the current mid

Why left + (right - left) // 2?

Using (left + right) // 2 can cause integer overflow when left and right are large:

  • If left = 2^31 - 1 and right = 2^31 - 1, then left + right exceeds INT_MAX
  • left + (right - left) // 2 is mathematically equivalent but avoids overflow

Example Walkthrough

Problem: Find 7 in [1, 3, 5, 7, 9, 11, 13, 15]

trace through this step by step. We start with the entire array as our search space, with left=0 pointing to the first element and right=7 pointing to the last element. The array has 8 elements, so our initial search space contains indices 0 through 7. In the first iteration, we calculate mid = 0 + (7 - 0) // 2 = 3, which gives us the middle element. We compare nums[3] = 7 with our target value 7, and they match perfectly. Since we found an exact match, we immediately return index 3. This demonstrates the best-case scenario where binary search finds the target in constant time.

1
2
Initial: left=0, right=7
Iteration 1: mid=3, nums[3]=7 == 7 → Found at index 3

Problem: Find 6 in [1, 3, 5, 7, 9, 11, 13, 15]

This example demonstrates a more typical case where the target doesn't exist in the array. We start with the same initial boundaries. In the first iteration, mid=3 gives us nums[3]=7, which is greater than our target 6. Since the array is sorted in ascending order, we know that all elements to the right of index 3 (values 7, 9, 11, 13, 15) are also greater than 6, so we can safely eliminate the entire right half. We update right = mid - 1 = 2, effectively reducing our search space to indices 0 through 2.

In the second iteration, we calculate mid = 0 + (2 - 0) // 2 = 1, giving us nums[1]=3. This value is less than our target 6, so we eliminate the left half (indices 0 and 1) and update left = mid + 1 = 2. Now our search space contains only index 2.

In the third iteration, mid=2 gives us nums[2]=5, which is still less than 6. We update left = mid + 1 = 3. At this point, left=3 and right=2, which means left > right, violating our loop condition. This indicates that we've exhausted all possible positions where the target could exist, so we exit the loop and return -1 to indicate the target was not found.

1
2
3
4
5
Initial: left=0, right=7
Iteration 1: mid=3, nums[3]=7 > 6 → right=2 (eliminate right half)
Iteration 2: mid=1, nums[1]=3 < 6 → left=2 (eliminate left half)
Iteration 3: mid=2, nums[2]=5 < 6 → left=3 (eliminate current position)
Iteration 4: left=3 > right=2 → Exit, return -1

This walkthrough illustrates how binary search systematically narrows down the search space, eliminating half of the remaining possibilities at each step until either the target is found or we've confirmed it doesn't exist.

Boundary Handling: Left and Right Bound Templates

Many LeetCode problems require finding the first or last occurrence of a target, or the insertion position. These require modified templates.

Left Bound Template (First Occurrence)

Finds the leftmost position where target appears, or where it should be inserted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def left_bound(nums, target):
    """
    Find leftmost position of target.
    Returns index of first occurrence, or insertion position if not found.
    """
    left, right = 0, len(nums)  # Note: right = len(nums), not len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid  # Don't exclude mid, it might be the answer
    
    return left  # left is the insertion position

Key Differences: 1. Right boundary: right = len(nums) instead of len(nums) - 1 2. Loop condition: left < right instead of left <= right 3. Right update: right = mid instead of right = mid - 1 4. Return value: Returns left, which is the insertion position

Why these changes?

  • right = len(nums) allows returning insertion position beyond array
  • left < right ensures we don't miss the boundary case
  • right = mid keeps mid in search space (it might be the answer)

Right Bound Template (Last Occurrence)

Finds the rightmost position where target appears.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def right_bound(nums, target):
    """
    Find rightmost position of target.
    Returns index of last occurrence, or -1 if not found.
    """
    left, right = 0, len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] <= target:
            left = mid + 1  # Move right to find last occurrence
        else:
            right = mid
    
    # left is one position after the last occurrence
    if left == 0:
        return -1  # Target is smaller than all elements
    if nums[left - 1] != target:
        return -1  # Target not found
    return left - 1

Key Points:

  • When nums[mid] == target, we continue searching right (left = mid + 1)
  • After loop, left points to the position after the last occurrence
  • Return left - 1 if target exists, -1 otherwise

Visual Comparison

Finding target = 5 in [1, 3, 5, 5, 5, 7, 9]:

1
2
3
4
5
6
7
8
9
10
11
Left Bound:

- Returns index 2 (first occurrence)

Right Bound:

- Returns index 4 (last occurrence)

Standard Search:

- May return any of indices 2, 3, or 4 (implementation dependent)

Classic LeetCode Problems

Problem Statement: 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

Edge Cases:

  • Empty array: [] → Returns -1
  • Single element: [5], target 5 → Returns 0
  • Target not present: [1, 2, 3], target 4 → Returns -1
  • Target at boundaries: [1, 2, 3], target 1 or 3 → Returns 0 or 2

Time Complexity:Space Complexity:

LeetCode 35: Search Insert Position

Problem Statement: Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        
        return left

Example: 

1
2
3
4
5
6
7
8
nums = [1, 3, 5, 6], target = 5
→ Returns 2 (found at index 2)

nums = [1, 3, 5, 6], target = 2
→ Returns 1 (should be inserted at index 1)

nums = [1, 3, 5, 6], target = 7
→ Returns 4 (should be inserted at end)

Detailed Walkthrough for target = 2:

trace through the case where the target doesn't exist and we need to find the insertion position. We initialize left=0 and right=4 (note that right = len(nums), not len(nums) - 1, because we need to handle the case where the target should be inserted at the end).

In iteration 1, mid = 0 + (4 - 0) // 2 = 2. We compare nums[2]=5 with target 2. Since 5 >= 2, we set right = mid = 2 to search for the leftmost insertion position.

In iteration 2, left=0 and right=2, so mid = 0 + (2 - 0) // 2 = 1. We compare nums[1]=3 with target 2. Since 3 >= 2, we set right = mid = 1.

In iteration 3, left=0 and right=1, so mid = 0 + (1 - 0) // 2 = 0. We compare nums[0]=1 with target 2. Since 1 < 2, we set left = mid + 1 = 1.

Now left=1 equals right=1, so we exit the loop. The function returns left=1, which is indeed the correct insertion position: if we insert 2 at index 1, the array becomes [1, 2, 3, 5, 6], maintaining sorted order.

Key Insight: This is exactly the left bound template! The insertion position is the leftmost position where we could place the target. The template naturally handles all cases: when the target exists, it returns the first occurrence; when it doesn't exist, it returns where it should be inserted to maintain sorted order.

Time Complexity:Space Complexity:

LeetCode 34: Find First and Last Position

Problem Statement: Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found, return [-1, -1].

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def left_bound(nums, target):
            left, right = 0, len(nums)
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            return left
        
        def right_bound(nums, target):
            left, right = 0, len(nums)
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid
            return left - 1
        
        left_idx = left_bound(nums, target)
        
        # Check if target exists
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]
        
        right_idx = right_bound(nums, target)
        return [left_idx, right_idx]

Walkthrough for nums = [5, 7, 7, 8, 8, 10], target = 8:

This problem requires finding both the first and last occurrence of the target value 8 in an array that contains duplicates. The key insight is that we need to use two different binary search strategies: one to find the leftmost occurrence and another to find the rightmost occurrence.

Finding the Left Bound (First Occurrence):

We initialize left=0 and right=6 (note that right = len(nums), not len(nums) - 1, because we're using the left-bound template). Our goal is to find the leftmost position where we could insert the target value 8, which will be the first occurrence if it exists.

In iteration 1, we calculate mid = 0 + (6 - 0) // 2 = 3. However, wait — let me recalculate: mid = 0 + (6 - 0) // 2 = 3. Actually, let's trace more carefully. With left=0 and right=6, mid = 0 + (6 - 0) // 2 = 3. We check nums[3]=8, which equals our target. In the left-bound template, when nums[mid] >= target, we set right = mid to continue searching left, because mid itself might be the leftmost occurrence. So right=3.

In iteration 2, left=0 and right=3, so mid = 0 + (3 - 0) // 2 = 1. We check nums[1]=7, which is less than 8. Since we're looking for the leftmost position where the value is at least 8, we know everything to the left of index 1 is too small. We update left = mid + 1 = 2.

In iteration 3, left=2 and right=3, so mid = 2 + (3 - 2) // 2 = 2. We check nums[2]=7, which is still less than 8. We update left = mid + 1 = 3.

Now left=3 equals right=3, so we exit the loop. The left bound is 3, meaning the first occurrence of 8 is at index 3.

1
2
3
4
5
6
7
Left Bound:

- Initial: left=0, right=6
- Iteration 1: mid=3, nums[3]=8 >= 8 → right=3 (keep searching left)
- Iteration 2: mid=1, nums[1]=7 < 8 → left=2 (eliminate left portion)
- Iteration 3: mid=2, nums[2]=7 < 8 → left=3 (eliminate current position)
- left=3 == right=3 → Exit, return 3

Finding the Right Bound (Last Occurrence):

For the right bound, we want to find the rightmost occurrence. We use a different strategy: when nums[mid] <= target, we continue searching right by setting left = mid + 1, because we want to find the last occurrence.

In iteration 1, left=0 and right=6, mid=3. nums[3]=8 <= 8, so we set left = mid + 1 = 4 to continue searching right.

In iteration 2, left=4 and right=6, mid=5. nums[5]=10 > 8, so we set right=5 to search left.

In iteration 3, left=4 and right=5, mid=4. nums[4]=8 <= 8, so we set left = mid + 1 = 5.

Now left=5 equals right=5, so we exit. The right bound algorithm returns left - 1 = 4, which is the last occurrence of 8.

1
2
3
4
5
6
7
Right Bound:

- Initial: left=0, right=6
- Iteration 1: mid=3, nums[3]=8 <= 8 → left=4 (keep searching right)
- Iteration 2: mid=5, nums[5]=10 > 8 → right=5 (search left)
- Iteration 3: mid=4, nums[4]=8 <= 8 → left=5 (keep searching right)
- left=5 == right=5 → Exit, return 4 (left - 1)

Result: [3, 4]

After finding both bounds, we verify that the target exists by checking if nums[left_idx] == target. Since nums[3] == 8, we confirm the target exists and return [3, 4] as the range of occurrences.

Time Complexity:Space Complexity:

LeetCode 33: Search in Rotated Sorted Array

Problem Statement: There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is rotated at an unknown pivot index. Given the target value, return the index of target in nums, or -1 if it is not in nums.

Key Insight: Even though the array is rotated, at least one half is always sorted. We can use this property to eliminate half the search space.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
            
            # Left half is sorted
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

Visualization:

This problem demonstrates one of the most elegant applications of binary search: even when an array isn't fully sorted, we can still use binary search by identifying which half maintains sorted order. The key insight is that in a rotated sorted array, at least one half is always sorted, and we can use this property to eliminate half the search space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Rotated array: [4, 5, 6, 7, 0, 1, 2]
Target: 0

Step 1: mid=3, nums[3]=7
        We check if the left half is sorted: nums[0]=4 <= nums[3]=7 ✓
        Left half [4,5,6,7] is sorted
        Is target 0 in the sorted left half's range [4,7]? No
        Therefore, target must be in the right half
        → Search right half: left=4

Step 2: mid=5, nums[5]=1
        We check if the left half is sorted: nums[4]=0 <= nums[5]=1 ✓
        Actually, let's check the right half: nums[5]=1 > nums[6]=2 ✗
        So the right half [1,2] is sorted (but let's verify: nums[5]=1 <= nums[6]=2 ✓)
        Wait, let me reconsider. With left=4, right=6, mid=5:
        Check left half [4,5]: nums[4]=0 <= nums[5]=1 ✓, so left half is sorted
        Is target 0 in [0,1]? Yes!
        → Search left: right=4

Step 3: mid=4, nums[4]=0 == 0 → Found!

Let me provide a clearer step-by-step visualization:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Array: [4, 5, 6, 7, 0, 1, 2]
Indices: 0  1  2  3  4  5  6
Target: 0

Initial: left=0, right=6

Iteration 1:
  mid = 3, nums[3] = 7
  Check: nums[left]=4 <= nums[mid]=7? Yes → Left half [0..3] is sorted
  Is target in sorted left half range [4,7]? No (0 < 4)
  → Target must be in right half [4..6]
  Update: left = 4

Iteration 2:
  left=4, right=6
  mid = 5, nums[5] = 1
  Check: nums[left]=0 <= nums[mid]=1? Yes → Left half [4..5] is sorted
  Is target in sorted left half range [0,1]? Yes (0 is in [0,1])
  → Target is in left half [4..5]
  Update: right = 4

Iteration 3:
  left=4, right=4
  mid = 4, nums[4] = 0
  nums[4] == target → Found at index 4!

This visualization shows how we systematically eliminate half the search space at each step, even though the array is rotated. The critical observation is that by checking which half is sorted and whether the target falls within that sorted half's range, we can always eliminate half the possibilities.

Edge Cases:

  • Not rotated: [1, 2, 3, 4, 5] → Works normally
  • Fully rotated: [5, 1, 2, 3, 4] → Handled correctly
  • Single element: [1] → Returns correct index
  • Target not present: Returns -1

Time Complexity:Space Complexity:

LeetCode 162: Find Peak Element

Problem Statement: A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that `nums[-1] = nums[n] = -$.

Key Insight: We can use binary search even though the array isn't sorted! If nums[mid] < nums[mid + 1], there must be a peak on the right (because we can always go up). Similarly, if nums[mid] > nums[mid + 1], there's a peak on the left.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] < nums[mid + 1]:
                # Peak is on the right
                left = mid + 1
            else:
                # Peak is on the left (including mid)
                right = mid
        
        return left

Visualization:

This problem is fascinating because it demonstrates that binary search doesn't always require a fully sorted array. Instead, it relies on a specific property: if we're on an upward slope, there must be a peak to the right; if we're on a downward slope, there must be a peak to the left (or we're already at a peak).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Array: [1, 2, 3, 1]
Indices: 0  1  2  3

Initial: left=0, right=3

Step 1: mid=1, nums[1]=2
        Compare: nums[1]=2 < nums[2]=3
        We're on an upward slope → Peak must be to the right
        Reasoning: Since nums[2] > nums[1], and we can continue going right,
                   and we know nums[n] = -∞, there must be a peak somewhere to the right
        → Move right: left=2

Step 2: left=2, right=3
        mid=2, nums[2]=3
        Compare: nums[2]=3 > nums[3]=1
        We're on a downward slope → Peak is to the left (possibly at current position)
        Reasoning: Since nums[2] > nums[3], we're going down. The peak could be
                   at index 2 itself, or somewhere to the left. Since nums[-1] = -∞,
                   there must be a peak in the left portion including index 2.
        → Move left: right=2

Step 3: left=2 == right=2 → Exit
        Return: 2 (which is indeed a peak: 3 > 2 and 3 > 1)

Why this works: The key insight is that we can always make progress toward a peak. If nums[mid] < nums[mid + 1], we know we're ascending, and since the boundary is -∞, there must be a peak ahead. If nums[mid] > nums[mid + 1], we're descending, and the peak is behind us (possibly at mid itself). This property guarantees that binary search will converge to a peak.

Why This Works:

  • If nums[mid] < nums[mid + 1], we're on an upward slope. Since nums[n] = -\infty, there must be a peak to the right.
  • If nums[mid] > nums[mid + 1], we're on a downward slope. Since nums[-1] = -\infty, there must be a peak to the left (possibly at mid).

Time Complexity:Space Complexity:

LeetCode 74: Search a 2D Matrix

Problem Statement: Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right
  • The first integer of each row is greater than the last integer of the previous row

Approach 1: Treat as 1D Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            row, col = mid // n, mid % n
            
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return False

Approach 2: Two Binary Searches

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        
        # Binary search for row
        top, bottom = 0, len(matrix) - 1
        while top < bottom:
            mid = top + (bottom - top) // 2
            if matrix[mid][0] <= target <= matrix[mid][-1]:
                top = bottom = mid
                break
            elif matrix[mid][0] > target:
                bottom = mid - 1
            else:
                top = mid + 1
        
        # Binary search within row
        row = top
        left, right = 0, len(matrix[row]) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return False

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Matrix:
[
  [1,  3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]
Target: 3

Approach 1:

- Treat as [1,3,5,7,10,11,16,20,23,30,34,60]
- Binary search finds index 1 → row=0, col=1 → Found!

Approach 2:

- Find row: target 3 is in row 0
- Search row 0: Found at index 1

Time Complexity:for approach 1,for approach 2
Space Complexity:

LeetCode 240: Search a 2D Matrix II

Problem Statement: Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right
  • Integers in each column are sorted in ascending from top to bottom

Key Insight: Unlike Problem 6, we can't treat this as a 1D array because rows don't connect seamlessly. However, we can use a clever approach: start from the top-right corner and eliminate one row or column at a time.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        
        m, n = len(matrix), len(matrix[0])
        # Start from top-right corner
        row, col = 0, n - 1
        
        while row < m and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                # Current element is too large, eliminate this column
                col -= 1
            else:
                # Current element is too small, eliminate this row
                row += 1
        
        return False

Visualization:

This problem requires a clever insight: we can't use standard binary search because the matrix doesn't have the same properties as Problem 6. However, by starting from the top-right corner, we can eliminate either an entire row or an entire column with each comparison, guaranteeing progress.

The key observation is that from the top-right corner:

  • All elements to the left are smaller (because rows are sorted left-to-right)
  • All elements below are larger (because columns are sorted top-to-bottom)
  • This property allows us to eliminate either a row or column at each step
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Matrix:
[
  [1,  4,  7,  11, 15],
  [2,  5,  8,  12, 19],
  [3,  6,  9,  16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Target: 5

Step 1: Start at (0, 4) = 15
        Compare: 15 > 5
        Since 15 > 5 and the column is sorted top-to-bottom,
        all elements below (15) in this column are also > 5
        → Eliminate entire column 4, move left: col = 3

Step 2: At (0, 3) = 11
        Compare: 11 > 5
        Same reasoning: all elements below 11 in column 3 are > 5
        → Eliminate entire column 3, move left: col = 2

Step 3: At (0, 2) = 7
        Compare: 7 > 5
        All elements below 7 in column 2 are > 5
        → Eliminate entire column 2, move left: col = 1

Step 4: At (0, 1) = 4
        Compare: 4 < 5
        Since 4 < 5 and the row is sorted left-to-right,
        all elements to the left of 4 in this row are also < 5
        → Eliminate entire row 0, move down: row = 1

Step 5: At (1, 1) = 5
        Compare: 5 == 5 → Found!

This approach is elegant because it guarantees that we eliminate either a row or column at each step. In the worst case, we eliminate all rows and columns except one, giving ustime complexity, which is optimal for this problem structure. Key: recognizing the sorted properties of both rows and columns and leveraging them to make progress in two dimensions simultaneously.

Why This Works:

  • Starting from top-right, all elements to the left are smaller, all elements below are larger
  • If matrix[row][col] > target, everything in this column below is also larger → eliminate column
  • If matrix[row][col] < target, everything in this row to the left is also smaller → eliminate row
  • Each comparison eliminates either a row or a column, guaranteeing progress

Time Complexity: - at mostcomparisons
Space Complexity:

LeetCode 658: Find K Closest Elements

Problem Statement: Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order. An integer a is closer to x than an integer b if |a - x| < |b - x|, or |a - x| == |b - x| and a < b.

Key Insight: We need to find the left boundary of the window containing k closest elements. We can use binary search to find the optimal starting position.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # Binary search for the left boundary of the window
        left, right = 0, len(arr) - k
        
        while left < right:
            mid = left + (right - left) // 2
            
            # Compare distances: if arr[mid+k] is closer than arr[mid], move right
            # We want to minimize the distance, so if right side is better, move left
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        
        return arr[left:left + k]

Explanation:

  • We're searching for the left boundary of a window of size k
  • The search space is [0, len(arr) - k] because we need k elements
  • At each step, compare arr[mid] and arr[mid + k]:
    • If x - arr[mid] > arr[mid + k] - x, the right side is closer → move left boundary right
    • Otherwise, the left side is closer or equal → keep searching left

Example:

This problem requires finding a window of k elements that are closest to x. The key insight is that we can use binary search to find the optimal starting position of this window. We compare the distances from x to the leftmost and rightmost elements of a candidate window to determine which direction to search.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
arr = [1, 2, 3, 4, 5], k = 4, x = 3

We need to find 4 closest elements to 3. The possible windows are:

- Window starting at 0: [1, 2, 3, 4] → distances: |1-3|=2, |2-3|=1, |3-3|=0, |4-3|=1
- Window starting at 1: [2, 3, 4, 5] → distances: |2-3|=1, |3-3|=0, |4-3|=1, |5-3|=2

Initial: left = 0, right = 1 (len - k = 5 - 4 = 1)
         We can only start windows at positions 0 or 1 (since we need 4 elements)

Iteration 1: mid = 0
             Consider window starting at mid=0: [arr[0], arr[1], arr[2], arr[3]] = [1, 2, 3, 4]
             Compare distances:

               - Distance from x to leftmost: x - arr[0] = 3 - 1 = 2
               - Distance from x to rightmost: arr[0+k] - x = arr[4] - x = 5 - 3 = 2
             
             The comparison x - arr[mid] > arr[mid + k] - x checks:

               - If the rightmost element is closer than the leftmost, move window right
               - If leftmost is closer or equal, keep searching left
             
             Here: 2 > 2? No → The leftmost element is not significantly farther
             → Keep searching left (or stay): right = 0

left = 0 == right = 0 → Exit
Return arr[0:4] = [1, 2, 3, 4]

Verification: The window [1, 2, 3, 4] has elements with distances [2, 1, 0, 1] from x=3.
              The alternative window [2, 3, 4, 5] has distances [1, 0, 1, 2].
              Both have the same maximum distance (2), but [1, 2, 3, 4] is chosen because
              when distances are equal, we prefer the smaller element (1 < 2).

This example demonstrates how binary search can be applied to optimization problems where we're searching for an optimal position rather than a specific value. The comparison logic x - arr[mid] > arr[mid + k] - x elegantly determines which direction contains the better window.

Time Complexity: - binary search + slicing
Space Complexity:excluding output array

Binary Search on Answer

Sometimes, the problem doesn't explicitly ask for binary search, but we can use it to search for the answer in a solution space.

Concept

Instead of searching in an array, we search for the optimal answer in a range of possible values. This works when: 1. We can check if a candidate answer is valid 2. The validity function is monotonic (if answeris valid, then allare valid, or vice versa)

LeetCode 875: Koko Eating Bananas

Problem Statement: Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Koko wants to finish eating all the bananas before the guards return. Return the minimum integer k such that she can eat all the bananas within h hours.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def can_finish(speed):
            """Check if Koko can finish with given speed."""
            hours = 0
            for pile in piles:
                hours += (pile + speed - 1) // speed  # Ceiling division
                if hours > h:
                    return False
            return True
        
        # Binary search on answer: speed ranges from 1 to max(piles)
        left, right = 1, max(piles)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if can_finish(mid):
                # This speed works, try smaller
                right = mid
            else:
                # This speed is too slow
                left = mid + 1
        
        return left

Key Insight:

  • We're not searching in an array, but in the solution space of possible speeds [1, max(piles)]
  • If speedallows finishing in time, then all speedsalso work (monotonic property)
  • We want the minimum valid speed, so we use the left bound template

Example:

This problem demonstrates binary search on answer space beautifully. We're not searching in an array of speeds, but rather searching for the optimal speed value in a continuous range. Key: recognizing that if a certain speed works, all faster speeds also work (monotonic property), so we can use binary search to find the minimum valid speed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
piles = [3, 6, 7, 11], h = 8

We need to find the minimum speed that allows finishing in 8 hours.

Check speed = 4:

- Pile 3: ⌈3/4⌉ = 1 hour (ceiling division: 3 bananas / 4 per hour = 0.75, rounded up = 1)
- Pile 6: ⌈6/4⌉ = 2 hours (6 / 4 = 1.5, rounded up = 2)
- Pile 7: ⌈7/4⌉ = 2 hours (7 / 4 = 1.75, rounded up = 2)
- Pile 11: ⌈11/4⌉ = 3 hours (11 / 4 = 2.75, rounded up = 3)
- Total: 1 + 2 + 2 + 3 = 8 hours → Valid!

Check speed = 3:

- Pile 3: ⌈3/3⌉ = 1 hour
- Pile 6: ⌈6/3⌉ = 2 hours
- Pile 7: ⌈7/3⌉ = 3 hours (7 / 3 = 2.33, rounded up = 3)
- Pile 11: ⌈11/3⌉ = 4 hours (11 / 3 = 3.67, rounded up = 4)
- Total: 1 + 2 + 3 + 4 = 10 hours → Invalid (exceeds 8 hours)

Binary search process:

- Search space: [1, 11] (minimum possible speed is 1, maximum needed is max(piles) = 11)
- Check mid = 6: Can finish in time? Yes → Try smaller, right = 6
- Check mid = 3: Can finish in time? No → Need faster, left = 4
- Check mid = 4: Can finish in time? Yes → Try smaller, right = 4
- left = 4 == right = 4 → Exit, minimum speed = 4

This example illustrates the power of binary search on answer space: instead of checking every possible speed from 1 to 11 (which would be 11 checks), binary search finds the answer in only 4 checks, demonstrating logarithmic efficiency even when the answer space isn't explicitly an array.

Time Complexity:Space Complexity:

More Binary Search on Answer Problems

  1. Split Array Largest Sum (LeetCode 410): Binary search on the maximum sum
  2. Capacity To Ship Packages (LeetCode 1011): Binary search on ship capacity
  3. Minimize Maximum Distance to Gas Station (LeetCode 774): Binary search on maximum distance
  4. Kth Smallest Number in Multiplication Table (LeetCode 668): Binary search on the answer value

Common Mistakes and Debugging Tips

Mistake 1: Infinite Loops

Problem: Using left < right with right = mid - 1

1
2
3
4
5
6
7
# WRONG
while left < right:
    mid = left + (right - left) // 2
    if nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1  # Can cause infinite loop!

Fix: Match loop condition with boundary updates:

  • left <= right → use right = mid - 1
  • left < right → use right = mid

Mistake 2: Off-by-One Errors

Problem: Returning wrong index

1
2
3
4
5
# WRONG for insertion position
def searchInsert(nums, target):
    left, right = 0, len(nums) - 1  # Should be len(nums)
    # ...
    return right  # Should return left

Fix: Understand what each template returns:

  • Left bound template returns insertion position
  • Right bound template returns left - 1 for last occurrence

Mistake 3: Integer Overflow

Problem: Using (left + right) // 2

1
2
3
4
5
# WRONG (can overflow)
mid = (left + right) // 2

# CORRECT
mid = left + (right - left) // 2

Mistake 4: Not Handling Empty Arrays

Problem: Accessing nums[0] without checking

1
2
3
4
5
6
7
8
9
10
11
# WRONG
def search(nums, target):
    left, right = 0, len(nums) - 1
    # If nums is empty, len(nums) - 1 = -1, and nums[-1] is wrong!

# CORRECT
def search(nums, target):
    if not nums:
        return -1
    left, right = 0, len(nums) - 1
    # ...

Debugging Tips

  1. Print mid and boundaries: Add print statements to track search progress 

    1
    2
    3
    4
    while left <= right:
        mid = left + (right - left) // 2
        print(f"left={left}, right={right}, mid={mid}, nums[mid]={nums[mid]}")
        # ...

  2. Test edge cases:

    • Empty array
    • Single element
    • Two elements
    • Target at boundaries
    • Target not present
    • Duplicate elements (for left/right bound problems)

  3. Verify loop invariants:

    • At each iteration, the answer (if exists) is in [left, right]
    • The loop terminates (boundaries converge)

  4. Check return value: Make sure you're returning the correct variable (left, right, mid, or left - 1)

Complexity Analysis Deep Dive

Why Logarithmic?

Binary search's efficiency comes from the exponential reduction of the search space. prove the time complexity more rigorously.

Recurrence Relation:

Solving the recurrence:

- - - - ... -Substituting back:Therefore,.

Space Complexity

Iterative:

  • Only uses a constant number of variables: left, right, mid

  • Space: Recursive:

  • Each recursive call adds one frame to the stack

  • Maximum depth:

  • Space:

Comparison with Other Search Methods

Method Time Complexity Space Complexity Requirements
Linear Search None
Binary Search Sorted array
Hash Table average None

When to use Binary Search:

  • Array is sorted (or can be sorted)
  • Need to find exact match, range, or insertion position
  • Memory is constrained (hash table uses more space)
  • Need to solve "binary search on answer" problems

Q&A: Common Questions

Q1: When should I use left <= right vs left < right?

A: This is one of the most common sources of confusion in binary search. The choice between these two conditions fundamentally changes how the algorithm behaves and what it returns.

Use left <= right when you want to check every position including when left == right. This is the standard template for finding an exact match, where you need to verify every possible position before concluding the target doesn't exist. The loop continues until the search space is completely exhausted, meaning left has moved past right.

Use left < right when you're using the left-bound or right-bound template, where left will converge to the answer position. In these templates, you're not looking for an exact match but rather a boundary position. The loop terminates when left equals right, at which point left (or left - 1 for right-bound) contains the answer.

Detailed Example:

Consider searching for target 5 in array [1, 3, 5, 7, 9]:

With left <= right:

  • The loop continues until left > right
  • You check position mid when left == right
  • This ensures you don't miss the target if it's at the boundary

With left < right:

  • The loop stops when left == right
  • You never check the final position where left == right inside the loop
  • This works for boundary-finding because left converges to the boundary position

When to use each:

  • Standard search: left <= right (check all positions, return mid or -1)
  • Insertion position: left < right (left converges to insertion point)
  • First occurrence: left < right (left converges to first occurrence)
  • Last occurrence: left < right (left converges to position after last occurrence)

Q2: Why do we use right = mid instead of right = mid - 1 in left-bound template?

A: This is a critical distinction that many programmers struggle with. The reason is that mid itself might be the answer we're looking for, and we need to keep it in the search space to ensure we find the leftmost occurrence.

When nums[mid] == target, we've found an occurrence of the target, but we don't know if it's the leftmost one. There could be more occurrences to the left. If we set right = mid - 1, we would exclude mid from consideration, potentially losing the correct answer. By setting right = mid, we keep mid in the search space while eliminating everything to its right.

Detailed walkthrough:

Consider finding the leftmost occurrence of 5 in [3, 5, 5, 5, 7]:

  • Initial: left=0, right=5
  • Iteration 1: mid=2, nums[2]=5 == 5
    • If we use right = mid - 1 = 1: We'd exclude index 2, but index 2 might be the answer (though we know index 1 is actually the leftmost)
    • If we use right = mid = 2: We keep index 2 in the search space and continue searching left
  • Iteration 2: mid=1, nums[1]=5 == 5
    • We set right = mid = 1 to continue searching left
  • Iteration 3: mid=0, nums[0]=3 < 5
    • We set left = mid + 1 = 1
  • Now left=1 == right=1, exit. The answer is left=1, which is correct.

Key insight: In the left-bound template, we're searching for the leftmost position where nums[pos] >= target. The position mid itself satisfies this condition, so we must keep it in the search space. Setting right = mid ensures we don't lose valid answers while still making progress toward the leftmost position.

Q3: How do I know which template to use?

A:

  • Standard template: Finding exact match, any occurrence
  • Left-bound template: Finding first occurrence, insertion position, minimum valid answer
  • Right-bound template: Finding last occurrence, maximum valid answer

Q4: Can binary search work on unsorted arrays?

A: Generally no, but there are exceptions:

  • Peak element: Works because of the specific property (at least one half has a peak)
  • Rotated sorted array: Works because at least one half is sorted
  • Binary search on answer: Works when the validity function is monotonic

Q5: What if the array has duplicates?

A: Standard binary search may return any occurrence. Use left-bound or right-bound templates to find specific occurrences. Key: understanding what happens when nums[mid] == target:

  • Left-bound: right = mid (keep searching left)
  • Right-bound: left = mid + 1 (keep searching right)

Q6: How do I handle negative numbers or very large numbers?

A: Binary search works the same way. Key: using left + (right - left) // 2 to avoid overflow. For very large arrays, ensure your language's integer type can handle the indices.

A: This is a nuanced question that depends on several factors. While binary search has superior asymptotic complexity, real-world performance involves more than just big-O notation.

For large arrays, binary search is almost always faster. The logarithmic time complexity means that even for arrays with millions of elements, binary search requires only about 20-30 comparisons, compared to potentially millions for linear search.

However, there are important considerations:

  • Small arrays (): Linear search might be faster due to overhead. Binary search has more overhead per iteration (calculating mid, multiple comparisons), while linear search is simpler. For very small arrays, the constant factors matter more than the asymptotic complexity.

  • Cache locality: Linear search has better cache performance because it accesses memory sequentially. Modern CPUs are optimized for sequential access patterns, and linear search can benefit from prefetching and cache line utilization. Binary search jumps around in memory, which can cause more cache misses.

  • Setup cost: Binary search requires a sorted array. If your data isn't already sorted, you need to sort it first, which is. If you only need to search once, linear search might be faster overall. However, if you need to perform multiple searches, the one-time sorting cost is amortized across all searches.

  • Branch prediction: Modern CPUs use branch prediction to optimize code execution. Linear search has more predictable branching patterns (usually just "continue" until found), while binary search has less predictable branches that can hurt performance on some architectures.

Practical recommendation: Use binary search when:

  • The array is already sorted or will be searched multiple times
  • The array is reasonably large ()
  • You need guaranteedperformance

Use linear search when:

  • The array is very small ()
  • The array is unsorted and you only need to search once
  • Cache performance is critical and the array fits in cache

Q8: How do I modify binary search for descending arrays?

A: Simply reverse the comparison: 

1
2
3
4
5
6
if nums[mid] == target:
    return mid
elif nums[mid] > target:  # Reversed!
    left = mid + 1
else:
    right = mid - 1

Q9: What's the difference between mid = (left + right) // 2 and mid = left + (right - left) // 2?

A: Mathematically equivalent, but the second form prevents integer overflow:

  • First: left + right can overflow if both are large
  • Second: right - left is safer, then add to left

Q10: How do I debug a binary search that's not working?

A: 1. Add print statements for left, right, mid, and nums[mid] to track the search progress: 

1
2
3
4
while left <= right:
    mid = left + (right - left) // 2
    print(f"left={left}, right={right}, mid={mid}, nums[mid]={nums[mid]}")
    # ... rest of code

  1. Verify loop condition matches boundary updates:

    • left <= right → use right = mid - 1
    • left < right → use right = mid

  2. Check edge cases systematically:

    • Empty array: []
    • Single element: [1]
    • Two elements: [1, 2]
    • Target at boundaries: first or last element
    • Target doesn't exist: smaller than min or larger than max
    • Duplicate elements (for left/right bound problems)

  3. Ensure correct return value:

    • Standard search: return mid if found, -1 otherwise
    • Left bound: return left (but check bounds first)
    • Right bound: return left - 1 (but check bounds first)

  4. Verify array is sorted: Binary search only works on sorted arrays. If your code isn't working, double-check the input.

  5. Trace through examples with duplicates: For left/right bound problems, manually trace through examples like [1, 2, 2, 2, 3] with target 2.

  6. Check for infinite loops: If your code hangs, verify that boundaries are actually converging. Add a counter to detect infinite loops: 

    1
    2
    3
    4
    iterations = 0
    while left < right and iterations < 100:
        iterations += 1
        # ... rest of code

A: Floating-point binary search is similar but uses a tolerance to determine when to stop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search_float(func, target, left, right, tolerance=1e-9):
    """
    Find x such that func(x) == target (within tolerance).
    Assumes func is monotonic.
    """
    while right - left > tolerance:
        mid = (left + right) / 2.0
        
        if func(mid) < target:
            left = mid
        else:
            right = mid
    
    return (left + right) / 2.0

Key differences:

  • Use (left + right) / 2.0 instead of integer division
  • Loop condition: right - left > tolerance instead of left < right
  • No +1 or -1 in updates (floating-point doesn't need it)

Example: Finding square root with precision

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def sqrt_binary_search(x, precision=1e-9):
    if x < 0:
        return None
    if x == 0:
        return 0.0
    
    left, right = 0.0, float(x)
    
    while right - left > precision:
        mid = (left + right) / 2.0
        square = mid * mid
        
        if square < x:
            left = mid
        else:
            right = mid
    
    return (left + right) / 2.0

Q12: Can binary search be used for optimization problems?

A: Yes! Binary search is excellent for optimization problems where: 1. We can check if a solution is feasible 2. The feasibility function is monotonic

Example: Minimize Maximum Distance to Gas Station (LeetCode 774)

Given positions of gas stations and number of new stations to add, minimize the maximum distance between adjacent stations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def minmaxGasDist(stations, k):
    def can_achieve(max_dist):
        """Check if we can achieve max distance <= max_dist with k stations."""
        stations_needed = 0
        for i in range(len(stations) - 1):
            gap = stations[i + 1] - stations[i]
            stations_needed += int(gap / max_dist)
            if stations_needed > k:
                return False
        return True
    
    left, right = 0, max(stations[i + 1] - stations[i] for i in range(len(stations) - 1))
    
    while right - left > 1e-6:  # Floating-point tolerance
        mid = (left + right) / 2.0
        if can_achieve(mid):
            right = mid
        else:
            left = mid
    
    return left

Q13: How do I modify binary search for descending arrays?

A: Simply reverse the comparison operators:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search_descending(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:  # Reversed: in descending, larger means go right
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Key change: nums[mid] < target becomes nums[mid] > target because in descending order, larger values are to the left.

Q14: What's the relationship between binary search and divide-and-conquer?

A: Binary search is a special case of divide-and-conquer where:

  • Divide: Split the search space in half by comparing with the middle element
  • Conquer: Recursively search in the relevant half
  • Combine: Return the result (no combination needed, we just return what we find)

However, binary search is typically implemented iteratively for better space efficiency (vs).

Recursive version:

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search_recursive(nums, target, left, right):
    if left > right:
        return -1
    
    mid = left + (right - left) // 2
    
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search_recursive(nums, target, mid + 1, right)
    else:
        return binary_search_recursive(nums, target, left, mid - 1)

Iterative version (preferred):

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search_iterative(nums, target):
    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

Q15: How do I handle binary search when the array might have duplicates?

A: Use left-bound or right-bound templates depending on what you need:

  • Find first occurrence: Use left-bound template
  • Find last occurrence: Use right-bound template
  • Find any occurrence: Standard template works, but result is non-deterministic
  • Count occurrences: Find both bounds, then right_bound - left_bound + 1

Example: Count occurrences of target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def count_occurrences(nums, target):
    def left_bound(nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left
    
    def right_bound(nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left - 1
    
    left_idx = left_bound(nums, target)
    if left_idx == len(nums) or nums[left_idx] != target:
        return 0
    
    right_idx = right_bound(nums, target)
    return right_idx - left_idx + 1

Advanced Binary Search Patterns

Beyond the standard templates, there are several advanced patterns that appear frequently in competitive programming and technical interviews.

Pattern 1: Binary Search on Answer Space

We've already seen this with "Koko Eating Bananas," but it's worth exploring more deeply. The key insight is that we're not searching in an array, but in a solution space where we can verify if a candidate answer is valid.

When to Use:

  • Problem asks for "minimum maximum" or "maximum minimum"
  • We can check if a value satisfies the condition
  • The validity function is monotonic (ifworks, then allwork, or vice versa)

Template:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def binary_search_answer():
    # 1. Determine answer range
    left, right = min_possible, max_possible
    
    # 2. Binary search
    while left < right:
        mid = left + (right - left) // 2
        
        if is_valid(mid):
            # Try smaller (or larger, depending on problem)
            right = mid
        else:
            left = mid + 1
    
    return left

Example: Split Array Largest Sum (LeetCode 410)

Given an array nums and integer m, split nums into m non-empty subarrays such that the largest sum among these subarrays is minimized.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def can_split(max_sum):
            """Check if we can split into m subarrays with max sum <= max_sum."""
            subarrays = 1
            current_sum = 0
            
            for num in nums:
                if current_sum + num > max_sum:
                    subarrays += 1
                    current_sum = num
                    if subarrays > m:
                        return False
                else:
                    current_sum += num
            return True
        
        left, right = max(nums), sum(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            if can_split(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

Pattern 2: Binary Search with Custom Comparison

Sometimes, the comparison isn't straightforward. We need to define a custom comparison function.

Example: Search in Rotated Sorted Array with Duplicates (LeetCode 81)

When duplicates exist, nums[left] <= nums[mid] doesn't guarantee the left half is sorted. We need to handle the case where nums[left] == nums[mid].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return True
            
            # Handle duplicates: can't determine which half is sorted
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            elif nums[left] <= nums[mid]:
                # Left half is sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # Right half is sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return False

Pattern 3: Binary Search on Function Values

Instead of searching in an array, we search for a value where a function meets certain criteria.

Example: Sqrt(x) (LeetCode 69)

Find the integer square root of x without using built-in functions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        left, right = 1, x // 2
        
        while left < right:
            mid = left + (right - left + 1) // 2  # Use +1 to avoid infinite loop
            
            if mid * mid > x:
                right = mid - 1
            else:
                left = mid
        
        return left

Key Point: Notice mid = left + (right - left + 1) // 2. This ensures we don't get stuck when left = mid and right = left + 1.

Pattern 4: Binary Search with Two Pointers

Combine binary search with two pointers for more complex problems.

Example: 4Sum II (LeetCode 454) - Variant Approach

While this problem has a hash table solution, we can also use binary search by sorting and then using two pointers with binary search for the remaining two numbers.

Pattern 5: Binary Search on Index Range

Sometimes we need to search for an index that satisfies certain properties, not a value.

Example: H-Index II (LeetCode 275)

Given a sorted array of citations, find the h-index using binary search.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left, right = 0, n
        
        while left < right:
            mid = left + (right - left) // 2
            # Check if citations[mid] papers have at least citations[mid] citations
            if citations[mid] >= n - mid:
                right = mid
            else:
                left = mid + 1
        
        return n - left

Variations and Extensions

Variation 1: Search in Rotated Arrays

Even though rotated arrays are not fully sorted, at least one half is always sorted, which we can exploit for binary search.

Key Technique: 1. Determine which half is sorted: nums[left] <= nums[mid] means left half is sorted 2. Check if target is in the sorted half's range 3. If not in sorted half, search in the unsorted half

Extended Problems:

    1. Search in Rotated Sorted Array (no duplicates)
    1. Search in Rotated Sorted Array II (with duplicates, needs special handling)
    1. Find Minimum in Rotated Sorted Array
    1. Find Minimum in Rotated Sorted Array II (with duplicates)

2D matrices can also be searched using binary search by converting 2D indices to 1D indices.

Conversion Formulas:

  • 1D index idx → 2D coordinates: row = idx // n, col = idx % n
  • 2D coordinates (row, col) → 1D index: idx = row * n + col

Extended Problems:

    1. Search a 2D Matrix (first element of each row > last element of previous row)
    1. Search a 2D Matrix II (each row and column sorted, more complex)

Variation 3: Binary Search on Answer

When the answer lies in a range and we can check if a value satisfies the condition, we can binary search in the answer space.

Problem-Solving Steps: 1. Determine the answer range [left, right] 2. Write a check function check(mid): determine if mid satisfies the condition 3. Narrow the search range based on the check result 4. Return the optimal answer

Classic Problems:

    1. Koko Eating Bananas
    1. Split Array Largest Sum
    1. Capacity To Ship Packages Within D Days
    1. Minimum Number of Days to Make m Bouquets

Variation 4: Finding Peaks

Even if arrays aren't fully sorted, binary search can work if certain properties are satisfied (e.g., unimodal, bimodal).

Key Insight: Following the upward direction will always lead to a peak.

Extended Problems:

    1. Find Peak Element
    1. Peak Index in a Mountain Array

Common Mistakes and Debugging Tips

Mistake 1: Infinite Loops

Cause: Loop condition doesn't match boundary updates.

Wrong Example: 

1
2
3
4
5
6
7
# WRONG: Using left < right but right = mid - 1
while left < right:
    mid = left + (right - left) // 2
    if nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1  # Can cause infinite loop!

Fix:

  • If using left <= right, use right = mid - 1
  • If using left < right, use right = mid

Mistake 2: Index Out of Bounds

Cause: Not checking if index is within valid range before returning.

Wrong Example: 

1
2
3
4
5
def find_left_boundary(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        # ...
    return left  # WRONG: Didn't check if left is out of bounds

Fix: 

1
2
3
4
# Check if index is out of bounds
if left >= len(nums) or nums[left] != target:
    return -1
return left

Mistake 3: Integer Overflow

Cause: Using (left + right) // 2 to calculate midpoint.

Fix: Always use left + (right - left) // 2

Mistake 4: Incorrect Boundary Handling

Common Edge Cases:

  • Empty array: len(nums) == 0
  • Single element: len(nums) == 1
  • Target at array boundaries
  • Target doesn't exist and is smaller than min / larger than max
  • Array has duplicate elements

Debugging Tips:

  1. Print intermediate states: 

    1
    2
    3
    4
    while left <= right:
        mid = left + (right - left) // 2
        print(f"left={left}, right={right}, mid={mid}, nums[mid]={nums[mid]}")
        # ...

  2. Use assertions: 

    1
    2
    assert 0 <= left < len(nums), f"left={left} out of range"
    assert 0 <= right < len(nums), f"right={right} out of range"

  3. Test cases:

    • [] (empty array)
    • [1] (single element)
    • [1, 2, 3], target = 1 (at boundary)
    • [1, 2, 3], target = 0 (doesn't exist, smaller than min)
    • [1, 2, 2, 2, 3], target = 2 (with duplicates)

Practical Tips

How to Quickly Identify Binary Search Problems

Consider binary search when you see these characteristics: 1. Sorted array: Array is already sorted (or can be sorted) 2. Search target: Need to find a value, position, or value satisfying a condition 3. Time complexity requirement: Requirestime complexity 4. Answer range: Answer lies in a determined range (binary search on answer)

Decision Tree for Template Selection

1
2
3
4
5
What does the problem ask for?
├─ Find unique target value → Use standard template
├─ Find first occurrence → Use left-bound template
├─ Find last occurrence → Use right-bound template
└─ Find insertion position → Use left-bound template (return left)

Problem-Solving Steps

  1. Determine search space: Searching in array or answer range?
  2. Choose template: Select appropriate template based on problem requirements
  3. Determine loop condition: left <= right or left < right?
  4. Write comparison logic: How to update boundaries based on nums[mid] and target?
  5. Handle edge cases: Empty array, single element, target doesn't exist, etc.
  6. Verify answer: Check correctness of return value

Performance Optimization Tips

  1. Early termination: Return immediately if target is found
  2. Reduce comparisons: Merge similar condition checks
  3. Space optimization: If only index is needed, don't store full array

Combining with Other Algorithms

  1. Binary search + sliding window: Use binary search to determine optimal window size when size is uncertain
  2. Binary search + dynamic programming: Use binary search to optimize DP state transitions when searching is needed
  3. Binary search + greedy: Use binary search to verify greedy strategy when validation is needed

While binary search is fundamental to algorithm interviews, its true power lies in its widespread use across real-world systems. Understanding these applications helps you appreciate why this algorithm is so important and gives you insight into how major systems handle large-scale search operations efficiently.

Database Indexing and Query Optimization

Modern databases rely heavily on binary search for efficient data retrieval. When you create an index on a column in a database like PostgreSQL or MySQL, the database engine typically builds a B-tree or similar data structure that uses binary search principles for lookups.

How it works: When you execute a query like SELECT * FROM users WHERE id = 12345, the database doesn't scan every row. Instead, it uses the index structure, which is essentially a sorted array of key-value pairs. The database performs a binary search on this index to locate the exact position where id = 12345 would be, then uses that information to quickly retrieve the corresponding row from disk.

Performance impact: Without binary search, finding a record in a table with a billion rows would require scanning potentially billions of rows. With binary search on an index, the same operation requires only about 30 comparisons, reducing query time from minutes to milliseconds. This is why database administrators spend significant time designing proper indexes — they're leveraging binary search's logarithmic efficiency.

Example scenario: Consider an e-commerce platform storing millions of product records. When a customer searches for a product by its unique product ID, the database uses binary search on the product ID index to instantly locate the product, rather than scanning through millions of records sequentially.

Version Control Systems: Git Bisect

One of the most elegant applications of binary search is Git's bisect command, which helps developers find the exact commit that introduced a bug. This tool demonstrates binary search's power in problem-solving beyond simple array searching.

How it works: When you discover a bug in your codebase, you know it exists in the current version but didn't exist in some earlier version. Git bisect uses binary search to systematically narrow down which commit introduced the bug. You mark the current commit as "bad" and an earlier known-good commit as "good." Git then checks out the middle commit between these two points, and you test whether the bug exists. Based on your answer, Git eliminates half of the remaining commits and repeats the process.

Visualization: If you have 1000 commits between the good and bad versions, linear search would require checking up to 1000 commits. Binary search reduces this to at most 10 checks (since). This makes debugging large codebases with extensive commit histories dramatically more efficient.

Real-world impact: In large software projects with thousands of commits, manually checking each commit would be impractical. Git bisect makes it feasible to track down bugs introduced weeks or months ago, saving developers countless hours of debugging time.

System Design: Load Balancing and Resource Allocation

Binary search plays a crucial role in distributed systems design, particularly in load balancing and resource allocation scenarios. When systems need to distribute work across multiple servers or allocate resources efficiently, binary search helps find optimal configurations.

Load balancing example: Consider a system that needs to route requests to servers based on their current load. If servers are sorted by their current capacity, binary search can quickly identify which server has the appropriate capacity to handle a new request. This is more efficient than checking every server sequentially, especially in systems with hundreds or thousands of servers.

Resource allocation: In cloud computing platforms, when allocating virtual machines or containers, the system needs to find the smallest available resource that meets the requirements. By maintaining sorted lists of available resources and using binary search, cloud platforms can efficiently match requests to resources, optimizing utilization and reducing allocation time.

Search Engines and Information Retrieval

Search engines use binary search extensively in their indexing and retrieval systems. While the full-text search algorithms are more complex, binary search is fundamental to many underlying operations.

Inverted index lookup: Search engines build inverted indexes that map words to lists of documents containing those words. These lists are typically sorted by document ID or relevance score. When processing a search query, the engine uses binary search to quickly locate specific entries in these sorted lists, enabling fast intersection of multiple word lists to find documents matching complex queries.

Ranking and sorting: When search results need to be sorted by relevance, date, or other criteria, binary search helps maintain sorted order efficiently. This is particularly important when dealing with millions of search results that need to be ranked and presented to users in real-time.

Operating Systems: Memory Management

Operating systems use binary search principles in memory management, particularly in algorithms that manage free memory blocks or page tables.

Buddy system: Some memory allocators use a buddy system where free memory blocks are organized in sorted lists by size. When allocating memory, the system uses binary search to quickly find the smallest block that's large enough for the request, optimizing memory usage.

Page table lookups: In virtual memory systems, page tables need to be searched efficiently. While modern systems use more sophisticated structures like hash tables, binary search principles still apply in various lookup scenarios, especially in systems with limited memory where simpler structures are preferred.

Network Protocols and Routing

Binary search finds applications in network routing and protocol implementations, where efficient lookup of routing tables and protocol handlers is critical for performance.

Routing table lookup: Network routers maintain routing tables that need to be searched quickly to determine where to forward packets. While modern routers use more sophisticated data structures, binary search principles are fundamental to many routing algorithms, especially in software routers and network simulation systems.

Protocol version negotiation: When systems need to negotiate protocol versions or capabilities, they often maintain sorted lists of supported versions. Binary search enables efficient lookup to find the highest compatible version between two systems.

Game Development and Graphics

In game development, binary search is used for various optimization tasks, from collision detection to rendering optimizations.

Spatial partitioning: Game engines often partition space into sorted regions for efficient collision detection. Binary search helps quickly locate which spatial region contains a particular object, enabling efficient collision queries.

Animation and interpolation: When animating between keyframes or interpolating values, binary search can quickly locate the appropriate keyframe range for a given time value, especially when keyframes are stored in sorted arrays.

Financial Systems: Trading and Risk Management

Financial systems use binary search for various operations, from matching orders to calculating risk metrics.

Order book matching: In stock exchanges, buy and sell orders are typically maintained in sorted order books. Binary search enables fast lookup to find matching orders or determine the best available price, which is critical for high-frequency trading where microseconds matter.

Risk calculation: When calculating portfolio risk or performing stress tests, systems often need to search through sorted historical data. Binary search enables efficient lookup of historical prices, volatility measures, and other financial metrics.

Why These Applications Matter

Understanding these real-world applications helps you appreciate binary search beyond interview problems. When you encounter a problem that involves searching through sorted data, maintaining sorted order, or finding optimal values in a range, binary search should be one of the first algorithms you consider. The logarithmic time complexity makes it scalable to massive datasets, which is why it's foundational to so many critical systems.

Moreover, recognizing these patterns helps you identify opportunities to apply binary search in your own projects. Whether you're building a search feature, optimizing database queries, or designing a system that needs efficient lookups, binary search provides a powerful tool for achieving optimal performance.

Summary

Binary search is a powerful algorithm that achieves logarithmic time complexity by eliminating half the search space in each iteration. Mastering it requires:

  1. Understanding the fundamentals: How elimination works, why it's logarithmic
  2. Knowing the templates: Standard, left-bound, and right-bound
  3. Recognizing when to apply: Sorted arrays, rotated arrays, binary search on answer
  4. Avoiding common mistakes: Infinite loops, off-by-one errors, overflow
  5. Handling edge cases: Empty arrays, single elements, boundaries, duplicates

Key Takeaways:

  • Standard template: left <= right, right = mid - 1, returns mid or -1
  • Left-bound template: left < right, right = mid, returns left (insertion position)
  • Right-bound template: left < right, left = mid + 1, returns left - 1 (last occurrence)
  • Always use: mid = left + (right - left) // 2 to prevent overflow
  • Binary search on answer: Search solution space when validity is monotonic

Practice Problems by Difficulty:

Easy:

  • Binary Search (704)
  • Search Insert Position (35)
  • First Bad Version (278)

Medium:

  • Find First and Last Position (34)
  • Search in Rotated Sorted Array (33)
  • Find Peak Element (162)
  • Search a 2D Matrix (74)

Hard:

  • Split Array Largest Sum (410)
  • Koko Eating Bananas (875)
  • Capacity To Ship Packages (1011)

With practice, binary search becomes intuitive, and you'll recognize opportunities to apply it even in problems that don't explicitly mention searching. Key: identifying the monotonic property that allows elimination of half the solution space.

Binary search is a favorite topic in technical interviews because it tests multiple skills: algorithm knowledge, boundary handling, code quality, and problem-solving approach. Here's how to excel in binary search interview questions.

Before You Start Coding

  1. Clarify the problem: Ask questions to ensure you understand:

    • Is the array sorted? In what order (ascending/descending)?
    • Are there duplicate elements?
    • What should be returned (index, boolean, value, insertion position)?
    • What if the target doesn't exist?
    • Are there any constraints (array size, value range)?

  2. Discuss your approach: Explain your strategy before coding:

    • Which template will you use (standard, left-bound, right-bound)?
    • Why this template fits the problem?
    • How will you handle edge cases?

  3. Estimate complexity: Mention time and space complexity upfront to show you understand the algorithm's efficiency.

During Coding

  1. Use clear variable names: left, right, mid are standard and clear. Avoid abbreviations.

  2. Prevent overflow: Always use mid = left + (right - left) // 2 and mention why: 

    1
    2
    # Good: Mention overflow prevention
    mid = left + (right - left) // 2  # Prevents integer overflow

  3. Comment key decisions: Explain why you chose specific loop conditions or boundary updates: 

    1
    2
    3
    # Using left < right because we want left to converge to insertion position
    while left < right:
        # ...

  4. Handle edge cases explicitly: Don't assume the input is well-formed: 

    1
    2
    if not nums:
        return -1  # Handle empty array

  5. Think out loud: Explain your thought process as you code. This helps interviewers understand your reasoning and catch mistakes early.

After Coding

  1. Walk through examples: Trace through your code with examples:

    • Normal case: target exists
    • Edge cases: empty array, single element, target at boundaries
    • Special cases: duplicates (for left/right bound problems)

  2. Test your code: Mentally execute your code with test cases: 

    1
    2
    3
    # Example: Search for 5 in [1, 3, 5, 7, 9]
    # left=0, right=4
    # mid=2, nums[2]=5 == 5 → Found!

  3. Discuss optimizations: If time permits, mention potential optimizations:

    • Early termination when target is found
    • Reducing comparisons by combining conditions
    • Space optimizations if applicable

  4. Mention alternatives: Show you know other approaches:

    • "We could also use a hash table for O(1) lookup, but that requires O(n) space and the array must be sorted anyway for binary search to work."

Common Interview Scenarios

Scenario 1: "Find the first occurrence of target"

Your response should include:

  • "This is a left-bound problem, so I'll use the left-bound template"
  • "I'll use left-closed-right-open interval [left, right)"
  • "When nums[mid] == target, I'll set right = mid to continue searching left"
  • "After the loop, I need to check if left is valid and nums[left] == target"

Scenario 2: "Search in a rotated sorted array"

Your response should include:

  • "Even though the array is rotated, at least one half is always sorted"
  • "I'll check which half is sorted by comparing nums[left] and nums[mid]"
  • "If target is in the sorted half's range, search there; otherwise search the other half"
  • "Handle the edge case where nums[left] == nums[mid] (for duplicates)"

Scenario 3: "Find the minimum value in a rotated sorted array"

Your response should include:

  • "This is similar to peak finding - we can use binary search"
  • "Compare nums[mid] with nums[right] to determine which half contains the minimum"
  • "If nums[mid] < nums[right], the minimum is in the left half (including mid)"
  • "Otherwise, the minimum is in the right half"

Red Flags to Avoid

  1. Don't memorize without understanding: Interviewers can tell if you're just reciting code. Understand why each line is there.

  2. Don't skip edge cases: Always mention how you'll handle empty arrays, single elements, boundaries, etc.

  3. Don't ignore integer overflow: Always use the safe midpoint calculation, even in Python where it's less critical.

  4. Don't forget to verify: After coding, verify your solution works for the examples you discussed.

  5. Don't give up on debugging: If your code has a bug, stay calm and debug systematically:

    • Add print statements (mentally or on paper)
    • Trace through with a small example
    • Check your loop condition and boundary updates

Sample Interview Dialogue

Interviewer: "Given a sorted array with duplicates, find the first and last position of target."

You: "I'll use the left-bound and right-bound templates. Let me clarify: should I return [-1, -1] if target doesn't exist? [Interviewer confirms] Great. I'll implement two helper functions: left_bound and right_bound. The left-bound function uses left < right and right = mid when nums[mid] >= target. The right-bound function uses left = mid + 1 when nums[mid] <= target. After finding both bounds, I'll check if target exists, and return the range."

Interviewer: "Good approach. Can you code it?"

You: [Code with comments explaining key decisions]

Interviewer: "Walk me through with nums = [5, 7, 7, 8, 8, 10], target = 8."

You: "For left-bound: Initially left=0, right=6. mid=3, nums[3]=8 >= 8, so right=3. mid=1, nums[1]=7 < 8, so left=2. mid=2, nums[2]=7 < 8, so left=3. left=3 == right=3, exit. Left bound is 3. For right-bound: [similar walkthrough]. Right bound is 4. So the answer is [3, 4]."

Interviewer: "What's the time complexity?"

You: "Both binary searches are, so overall it's. Space is."

This approach demonstrates understanding, clear communication, and thoroughness - exactly what interviewers are looking for.

Additional Interview Dialogue Examples

Scenario 1: Handling Edge Cases

Interviewer: "How would you modify your solution if the array could be empty?"

You: "Good catch! I should add an early return at the beginning. If len(nums) == 0, I'll immediately return [-1, -1] since there's nothing to search. This prevents any index out of bounds errors and handles the edge case explicitly."

Interviewer: "What if the target is smaller than all elements?"

You: "In that case, the left-bound function would return left=0, but when we check nums[0] != target, we'd correctly return [-1, -1]. Similarly, if the target is larger than all elements, left_bound would return left=len(nums), and our check left_idx == len(nums) would catch this and return [-1, -1]. So the current implementation handles these cases correctly."

Scenario 2: Optimization Discussion

Interviewer: "Can you optimize this further?"

You: "A few potential optimizations come to mind. First, if we find the left bound and it's out of bounds or doesn't match the target, we can return [-1, -1] immediately without searching for the right bound, since we know the target doesn't exist. Second, if the array is very large and we're searching for a value that likely doesn't exist, we could first do a quick standard binary search to check existence before finding bounds. However, for most cases, the currentsolution is already optimal, and these optimizations might add complexity without significant benefit unless we have specific performance requirements."

Interviewer: "What if we needed to find the count of occurrences?"

You: "That's straightforward! Once we have both bounds, if the target exists, the count is simply right_idx - left_idx + 1. If the target doesn't exist (we return [-1, -1]), the count would be 0. This is actually more efficient than scanning the entire array, which would be, whereas finding bounds is."

Scenario 3: Alternative Approaches

Interviewer: "Could you solve this with a single binary search?"

You: "Interesting question! While it's theoretically possible to find both bounds in a single pass by tracking additional state, it would be more complex and wouldn't improve the time complexity — we'd still needtime. The two-pass approach is cleaner, easier to understand, and leverages well-known templates. However, if we really wanted a single pass, we could modify the binary search to track the leftmost and rightmost positions seen so far, but this adds complexity without clear benefits. I'd stick with the two-pass approach for maintainability."

Interviewer: "What if the array had millions of elements and we needed to do this search many times?"

You: "In that case, we might consider preprocessing. If we're searching for the same target multiple times, we could cache the results. If we're searching for different targets but the array doesn't change, we could build additional data structures like a hash map of value-to-range mappings, but that would requirespace. For a general solution that handles arbitrary targets, the binary search approach is still optimal. The logarithmic complexity means even with millions of elements, each search is very fast — about 20-30 comparisons."

  • Post title：LeetCode (5): Binary Search
  • Post author：Chen Kai
  • Create time：2023-06-15 00:00:00
  • Post link：https://www.chenk.top/en/leetcode-binary-search/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments