Algorithms
  • Master finding first and last occurrences in arrays with duplicates
  • Understand binary search on rotated sorted arrays
  • Learn lower_bound and upper_bound for finding insertion points
  • Apply binary search to 2D sorted matrices

Binary Search Variations

Basic binary search is great when you're looking for a single value in a sorted array. But what if there are duplicates? What if the array has been rotated? What if you need to find where a new element should go?

These are the questions that lead to binary search variations. The core idea—eliminate half the possibilities with each comparison—stays the same, but we tweak the details to handle different scenarios.

The Problem with Duplicates

Standard binary search finds a value, but if there are duplicates, you might get any of them. Search for 5 in [1, 3, 5, 5, 5, 7, 9] and you might get index 2, 3, or 4. Which one? Who knows.

Often, though, you need something specific: the first 5, or the last 5, or how many 5s there are. Standard binary search doesn't give you that control.

Finding the First Occurrence

The trick: when you find the target, don't stop. Keep searching left to see if there are earlier occurrences.

def find_first(arr, target):
    left = 0
    right = len(arr) - 1
    result = -1  # Track the best answer so far
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid       # Found one, but maybe there's an earlier one
            right = mid - 1    # Keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Let's trace through finding the first 5 in [1, 3, 5, 5, 5, 7, 9]:

Array: [1, 3, 5, 5, 5, 7, 9]
Target: 5

Step 1: left=0, right=6, mid=3
  arr[3] = 5 → Found it!
  result = 3
  But continue searching left: right = 2

Step 2: left=0, right=2, mid=1
  arr[1] = 3 < 5
  left = 2

Step 3: left=2, right=2, mid=2
  arr[2] = 5 → Found it again!
  result = 2  (update to earlier occurrence)
  right = 1

Step 4: left=2, right=1
  left > right, stop
  
Return result = 2 (the first occurrence)

The key difference from standard binary search: we don't return immediately when we find the target. We update result and keep looking.

Finding the Last Occurrence

Same idea, but search right instead of left:

def find_last(arr, target):
    left = 0
    right = len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid       # Found one, but maybe there's a later one
            left = mid + 1     # Keep searching right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Counting Occurrences

Now here's a neat trick: if you can find the first and last occurrence, you can count how many times something appears:

def count_occurrences(arr, target):
    first = find_first(arr, target)
    if first == -1:
        return 0  # Not found at all
    
    last = find_last(arr, target)
    return last - first + 1

If the first 5 is at index 2 and the last 5 is at index 4, there are 4 - 2 + 1 = 3 occurrences.

This is O(log n) instead of the O(n) you'd need if you counted them one by one.

Rotated Sorted Arrays

Here's a common interview question: imagine an array that was sorted, then rotated at some unknown point.

Original: [0, 1, 2, 4, 5, 6, 7]
Rotated at index 4: [4, 5, 6, 7, 0, 1, 2]

The array is still "mostly" sorted—it's sorted in two pieces. Can you still use binary search?

Yes, but you need to figure out which piece you're in.

The key insight: when you look at the middle element, one half of the array is definitely sorted normally, and the other half contains the rotation point. Figure out which half is sorted, then decide whether your target would be in that sorted half.

def search_rotated(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        
        # Check if left half is sorted
        if arr[left] <= arr[mid]:
            # Left half is sorted
            if arr[left] <= target < arr[mid]:
                # Target is in the sorted left half
                right = mid - 1
            else:
                # Target must be in the right half
                left = mid + 1
        else:
            # Right half must be sorted
            if arr[mid] < target <= arr[right]:
                # Target is in the sorted right half
                left = mid + 1
            else:
                # Target must be in the left half
                right = mid - 1
    
    return -1

Let's trace searching for 0 in [4, 5, 6, 7, 0, 1, 2]:

Array: [4, 5, 6, 7, 0, 1, 2]
Target: 0

Step 1: left=0, right=6, mid=3
  arr[3] = 7
  Is left half sorted? arr[0]=4 <= arr[3]=7, yes
  Is target in [4, 7)? 0 is not in [4, 7)
  Search right: left = 4

Step 2: left=4, right=6, mid=5
  arr[5] = 1
  Is left half sorted? arr[4]=0 <= arr[5]=1, yes
  Is target in [0, 1)? Yes, 0 is in [0, 1)
  Search left: right = 4

Step 3: left=4, right=4, mid=4
  arr[4] = 0
  Found it!

The trick is checking whether each half is sorted by comparing the endpoints to the middle.

Finding Insertion Points

Sometimes you don't care if an element exists—you want to know where it should go.

If you're inserting 5.5 into [1, 3, 5, 7, 9], it should go at index 3 (between 5 and 7).

This is called finding the "lower bound" or "insertion point."

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

This is subtly different from standard binary search:

  • We use right = len(arr) instead of len(arr) - 1
  • We use left < right instead of left <= right
  • When arr[mid] >= target, we set right = mid instead of right = mid - 1

These changes make the algorithm find the leftmost position where target could be inserted.

Let's find where 5.5 goes in [1, 3, 5, 7, 9]:

Array: [1, 3, 5, 7, 9]
Target: 5.5

Step 1: left=0, right=5, mid=2
  arr[2]=5 < 5.5
  left = 3

Step 2: left=3, right=5, mid=4
  arr[4]=9 >= 5.5
  right = 4

Step 3: left=3, right=4, mid=3
  arr[3]=7 >= 5.5
  right = 3

Step 4: left=3, right=3
  left == right, stop
  
Return 3 (insert at index 3)

There's also "upper bound," which finds the position after all equal elements. If you have [1, 3, 5, 5, 5, 7, 9] and search for 5, lower bound returns 2 (before the 5s) and upper bound returns 5 (after the 5s).

def upper_bound(arr, target):
    left = 0
    right = len(arr)
    
    while left < right:
        mid = (left + right) // 2
        
        if arr[mid] <= target:  # Note: <= instead of <
            left = mid + 1
        else:
            right = mid
    
    return left

The only difference from lower_bound is <= instead of <.

Searching in 2D

What about a 2D array where each row is sorted and each column is sorted?

[
  [1,  4,  7,  11],
  [2,  5,  8,  12],
  [3,  6,  9,  16],
  [10, 13, 14, 17]
]

You can't just flatten it and binary search—that would lose the column sorting. But you can use an elegant trick: start at the top-right corner.

def search_2d(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    row = 0
    col = len(matrix[0]) - 1  # Start at top-right
    
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1  # Move down
        else:
            col -= 1  # Move left
    
    return False

From the top-right, you can eliminate an entire row or column with each comparison:

  • If current element is too small, the target can't be in this row (everything to the left is smaller)
  • If current element is too large, the target can't be in this column (everything below is larger)

Searching for 9 in the matrix above:

Start at [0][3] = 11
11 > 9, move left to [0][2] = 7
7 < 9, move down to [1][2] = 8
8 < 9, move down to [2][2] = 9
Found it!

This is O(m + n) for an m×n matrix, which is pretty good.

The Pattern

All these variations follow the same meta-algorithm:

  1. Define what you're searching for (could be a value, a boundary, an insertion point)
  2. Set up your search space (usually left and right)
  3. In the loop, eliminate half the search space based on some comparison
  4. When the loop ends, left or your tracked result is the answer

The devil is in the details—exactly what you compare, how you update the boundaries, when you stop. But the core idea is always: cut the search space in half.

When to Use Which

  • Standard binary search: Finding a specific value, no duplicates
  • First/last occurrence: Finding boundaries with duplicates
  • Insertion point (lower/upper bound): Inserting into a sorted array, range queries
  • Rotated array search: When data has been rotated
  • 2D search: Sorted matrix problems

These variations come up constantly in interviews and real codebases. Databases use them for range queries. Memory allocators use them to find free blocks. Graphics systems use them for collision detection.

Mastering these variations means you can recognize when a problem can be solved in O(log n) instead of O(n), which can be the difference between a solution that works and one that times out.