Introduction to Binary Search

Binary search is a highly efficient searching algorithm used to find an element in a sorted array (or list). It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of theinterval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. This process continues until the value is found or the interval is empty. Understanding its core principles and common modifications is crucial for coding interviews.

Binary Search Variants & Patterns

First and Last Occurrence (Boundaries in Sorted Array)

Modified Template: Continue the search even after finding the target, adjusting the boundary to find the extreme occurrence. For the first occurrence, if arr[mid] == target, record mid and move the high pointer to mid - 1 (search left half); for the last occurrence, record mid and move low to mid + 1 (search right half) (geeksforgeeks.org). Other conditions remain the same (move low up if arr[mid] < target, or move high down if arr[mid] > target). This way, the loop only ends when the boundary crosses, and the last recorded index is the first/last position of the target.

Example Problem: Find First and Last Position of Element in Sorted Array (LeetCode 34) – Given a sorted array of integers (possibly with duplicates) and a target value, find the indices of the first and last occurrence of the target. If the target is not found, return [-1, -1].

# Python Code (Iterative)
def find_first(nums, target):
    res = -1
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            res = mid            # record index
            high = mid - 1       # go left to find earlier occurrence
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return res

def find_last(nums, target):
    res = -1
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            res = mid            # record index
            low = mid + 1        # go right to find later occurrence
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return res

# Example usage:
# nums = [1, 2, 2, 2, 3, 3, 3, 4]
# target = 3
# first_index = find_first(nums, target)
# last_index  = find_last(nums, target)
# result = [first_index, last_index] # Should be [4, 6]

Edge Cases:

• Array is empty (no indices to find, return [-1, -1]).
• Target less than the first element or greater than the last element (target not present at all).
• All values are the same (e.g. nums = [7,7,7,7]): if target equals that value, first index = 0 and last index = n-1; if target is different, result remains [-1, -1].
• Single-element array: if it matches target, it's both first and last; otherwise, answer is [-1,-1].

Search in Rotated Sorted Array

Modified Template: Adjust the binary search condition to account for the array’s rotation. Although the array is not fully sorted, one half of it is always sorted around the middle (algo.monster). Check which side is sorted by comparing values at mid vs. the ends. If the left half is sorted (e.g. arr[low] <= arr[mid]): then determine if the target lies in this left sorted range; if yes, discard the right half (high = mid - 1), otherwise discard the left half (low = mid + 1). If the right half is sorted (else case): check if target lies in the right half’s range; if yes, search right (low = mid + 1), otherwise search left (high = mid - 1) (scaler.in). Continue until the target is found or the range is exhausted.

Example Problem: Search in Rotated Sorted Array (LeetCode 33) – There is an array originally sorted in ascending order, but then rotated at an unknown pivot. Given such an array nums (with distinct values) and an integer target, return the index of target if it exists, otherwise return -1.

# Python Code (Iterative)
def search_rotated(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        # Determine which half is sorted
        if nums[low] <= nums[mid]:  # Left half is sorted
            if nums[low] <= target < nums[mid]:
                high = mid - 1  # target in left half
            else:
                low = mid + 1   # target in right half
        else:  # Right half is sorted
            if nums[mid] < target <= nums[high]:
                low = mid + 1   # target in right half
            else:
                high = mid - 1  # target in left half
    return -1

Edge Cases:

• No rotation (array is fully sorted ascending). The logic still works: one of the “halves” will just be the whole array. For example, nums = [1,2,3,4] (not rotated) and target in array – algorithm behaves like standard binary search.
• Pivot at extreme end (e.g. rotated n times, effectively same as no rotation, or rotated only once making the last element the smallest). The method correctly handles these as well.
• Array of size 1 (trivially returns index 0 if target matches, else -1).
• Target not present in the array (the loop will exhaust and return -1).
• Duplicates in array: The above approach assumes distinct elements. If duplicates are present (e.g. LeetCode 81 variant), the check for sorted half can be trickier (because nums[low] == nums[mid] can happen). In such cases, a common fix is to move low and high inward while they equal mid value, or worst-case fallback to linear check. This ensures the search still finds the correct segment but may degrade to O(n) in the worst case.

Peak Element in Mountain Array

Modified Template: Instead of searching for a specific value, we search for a position where the sequence goes from increasing to decreasing. At each step, compare the middle element with its next neighbor. If arr[mid] < arr[mid+1], it means we are on an upward slope, so the peak must lie to the right – move low up to mid + 1. Otherwise (if arr[mid] > arr[mid+1]), we are on a downward slope or at a peak, so move high down to mid (medium.com). This way, the search space is always narrowed toward the peak. Stop when low == high; that index is a peak. (This works because at least one peak always exists in such arrays, and the logic ensures we never discard the peak’s position.)

Example Problem: Find Peak Element (LeetCode 162) – A peak element is an element that is strictly greater than its neighbors. Given an array nums, find the index of any one peak element. You may assume nums[-1] = -∞ and nums[n] = -∞ (so the first and last elements can be peaks if they are greater than their single neighbor). The solution must run in O(log n) time.

# Python Code (Iterative)
def find_peak(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if nums[mid] < nums[mid + 1]:
            low = mid + 1   # peak is to the right of mid
        else:
            high = mid      # peak is at mid or to the left
    return low  # low == high at the peak index

Edge Cases:

• Single element array (nums = [X]): that element is trivially a peak (no neighbors), and the algorithm returns index 0.
• Strictly increasing array (e.g. [1,2,3,4]): the last element is the peak (4 > 3). The algorithm will move low rightward each time, ending with low == high at the last index.
• Strictly decreasing array (e.g. [4,3,2,1]): the first element is the peak. The algorithm will move high leftward each time, ending at index 0.
• Array with multiple peaks (e.g. [5,1,2,1,4,3] has peaks at 0 (5) and 4 (4)): the algorithm will find one of the peak indices (which one depends on the path taken, but either is a correct answer).
• Adjacent equal values: The problem definition assumes “strictly greater than neighbors” for peaks, so typically no two adjacent elements are equal in test cases. If equal neighbors do appear, this method still works by treating else branch as “greater or equal” – it will move toward the left side in the presence of a plateau. However, if the input allows flat plateaus, any index on a plateau is not a “strictly greater” peak, and the peak would be at one end of the plateau. The binary search would end up at one of those ends.

Matrix Search (2D Binary Search)

Modified Template: Treat the 2D matrix as a flattened sorted list. Given an m x n matrix with each row sorted and the first element of each row greater than the last element of the previous row, the entire matrix can be seen as a sorted array of length m*n (designgurus.io). Use binary search on index range [0 .. m*n - 1]. For a given mid index, map it to a matrix position by: row = mid // n and col = mid % n. Let val = matrix[row][col]. Then compare val with target and adjust the search range as usual: if val < target, search right half; if val > target, search left half (designgurus.io). Continue until the target is found or the range is empty. This approach runs in O(log(m*n)).

Example Problem: Search a 2D Matrix (LeetCode 74) – You are given an m x n integer matrix with the following properties: each row is sorted in ascending order, and each row’s first element is greater than the previous row’s last element. Given a target value, return true if target is found in the matrix, or false otherwise. (This is a common interview question for searching in a matrix.)

matrix = [
  [1,  3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]

# Python Code (Iterative)
def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False  # empty matrix edge case
    m, n = len(matrix), len(matrix[0])
    low, high = 0, m * n - 1
    while low <= high:
        mid = (low + high) // 2
        # map mid to 2D indices:
        row = mid // n
        col = mid % n
        val = matrix[row][col]
        if val == target:
            return True
        elif val < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

Edge Cases:

• Matrix is empty, or m or n is 0 (no elements to search; the function should return false immediately).
• Matrix with one row or one column (still handled by the algorithm, as it effectively becomes normal binary search in a 1D list).
• Target smaller than the very first element or greater than the last element of the matrix (the algorithm will correctly end up returning false after checking the appropriate mid).
• Target exactly equal to the first or last element (found at boundary either at the beginning or end of the search).
• When m*n is large, be mindful of potential overflow in other languages when computing mid (in Python this isn’t an issue). The formula mid = (low + high)//2 is standard, but using low + (high-low)//2 can guard against overflow in languages with fixed integer sizes.

Interactive Binary Search Animations