Modified Binary Search

1. Binary Search Easy

Problem

Given a sorted array of distinct integers and a target, return its index, or -1 if it is absent. Must be O(log n).

Approach

• Template A, closed range. Return as soon as the midpoint matches.
• The exit condition left > right means the range is empty and the target is not there.

Solution

def binary_search(nums: list[int], target: int) -> int:
    """Index of target in a sorted list of distinct integers, or -1.

    Args:
        nums: Ascending, distinct integers.
        target: The value to find.

    Returns:
        The index of target, or -1 if it is not present.

    Example:
        >>> binary_search([-1, 0, 3, 5, 9, 12], 9)
        4
    """
    # Closed range. 0 is the first index. len(nums) - 1 is the last index.
    left, right = 0, len(nums) - 1

    # Invariant: if target is in nums, its index is inside [left, right].
    # <= because left == right still leaves one candidate to check.
    while left <= right:
        # Overflow-safe form. Identical in Python, required in C++ or Java.
        # // 2: integer midpoint, rounds down.
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1          # + 1: mid and everything left of it is too small
        else:
            right = mid - 1         # - 1: mid and everything right of it is too large

    return -1                       # range is empty: -1 means "not present"

Walkthrough

nums = [-1, 0, 3, 5, 9, 12], target = 2:

Reading the figure. Blue cells are still in the range. Amber is mid. Red cells are discarded. Green is the answer. There is no green cell here. After the third step left passes right, the range is empty, and the loop exits with -1.

Why log n, precisely

The range starts at size n and at least halves each iteration, so after k iterations it is at most n / 2ᵏ. The loop stops when the size drops below 1, which needs k > log₂n. For a billion elements that is 30 iterations.

Edge cases to raise

• Empty array: right = -1, the loop never runs, returns -1.
• Single element, matching or not.
• Target smaller than everything, or larger than everything.
• Duplicates are excluded by the problem statement. If they existed, this returns an arbitrary matching index, which is the next problem.

2. Search in Rotated Sorted Array Medium

Problem

A sorted array of distinct values has been rotated at some unknown pivot, for example [4,5,6,7,0,1,2]. Find the index of a target, or -1. Must be O(log n).

The key observation

The reasoning is always about the sorted half, because that is the only half whose contents you can reason about from its two endpoints.

Solution

def search_rotated(nums: list[int], target: int) -> int:
    """Index of target in a rotated sorted array of distinct values, or -1.

    Args:
        nums: A sorted array rotated at an unknown pivot. Values are distinct.
        target: The value to find.

    Returns:
        Its index, or -1.

    Example:
        >>> search_rotated([4, 5, 6, 7, 0, 1, 2], 0)
        4
    """
    # Closed range. 0 is the first index. len(nums) - 1 is the last index.
    left, right = 0, len(nums) - 1

    # Invariant: if target is in nums, its index is inside [left, right].
    while left <= right:
        mid = left + (right - left) // 2    # // 2: integer midpoint, rounds down

        if nums[mid] == target:
            return mid

        # <= not <: when two elements remain, mid == left and they are equal.
        if nums[left] <= nums[mid]:
            # Left half [left, mid] is sorted, so its range is known exactly.
            # mid is excluded with < because we already know it is not target.
            if nums[left] <= target < nums[mid]:
                right = mid - 1     # - 1: target is in the left half, drop mid
            else:
                left = mid + 1      # + 1: target is not there, drop mid too
        else:
            # Then the right half [mid, right] must be the sorted one.
            if nums[mid] < target <= nums[right]:
                left = mid + 1      # + 1: target is in the right half, drop mid
            else:
                right = mid - 1     # - 1: target is not there, drop mid too

    return -1                       # range is empty: -1 means "not present"

Why nums[left] <= nums[mid] and not <

Walkthrough

nums = [4,5,6,7,0,1,2], target = 0:

Reading the figure. Blue cells are in range, amber is mid, red is discarded, green is the answer. The purple bracket marks the half that is sorted. In step 1, 0 is outside 4 to 7, so the whole left half goes. In step 2, 0 is inside 0 to 1, so the search keeps the left part.

The two-pass alternative

Find the rotation point with a separate binary search (the smallest element), then run a normal binary search on the correct segment. Two clean passes, still O(log n), and easier to get right under pressure. The one-pass version above is what most interviewers expect, but naming the two-pass option shows you have thought about the trade-off between cleverness and clarity.

Edge cases to raise

• Rotation of zero, so the array is plain sorted: the left half always tests as sorted, and it degenerates to ordinary binary search.
• Single element.
• Target at the rotation point, which is the array minimum. Worth tracing.
• Target absent.
• Duplicates: see the warning. Always ask.

3. Find First and Last Position of Element in Sorted Array Medium

Problem

Given a sorted array that may contain duplicates, return the first and last index of a target as [first, last], or [-1, -1] if it is absent. Must be O(log n).

Approach

• Do not find one occurrence and then walk outward. A run of a million identical values makes that O(n), which fails the requirement. This is the trap in the question.
• Run two boundary searches. Both are Template B, and both use the same helper.
• The neat trick: the last index of target is one before the first index of target + 1. So a single lower_bound helper, called twice, answers both halves. For non-integer values you would write a matching upper_bound instead.

Solution

def lower_bound(nums: list[int], target: int) -> int:
    """First index where nums[index] >= target, or len(nums) if there is none.

    This is the boundary template: the predicate "nums[i] >= target" is
    false then true, with exactly one flip, because nums is sorted.
    """
    # Half-open [left, right). 0 is the first index. right = len(nums) is one
    # past the end, so "every value is smaller" can return len(nums).
    left, right = 0, len(nums)

    # Invariant: nums[:left] are all < target. nums[right:] are all >= target.
    while left < right:
        mid = left + (right - left) // 2    # // 2 rounds down, so mid < right

        if nums[mid] < target:
            left = mid + 1            # + 1: mid fails, discard it
        else:
            right = mid               # mid might be the answer, keep it

    return left                       # left == right: the first index >= target


def search_range(nums: list[int], target: int) -> list[int]:
    """First and last index of target in a sorted array, or [-1, -1].

    Args:
        nums: Ascending integers, duplicates allowed.
        target: The value to locate.

    Returns:
        [first_index, last_index], or [-1, -1] if target is absent.

    Example:
        >>> search_range([5, 7, 7, 8, 8, 10], 8)
        [3, 4]
    """
    first = lower_bound(nums, target)

    # lower_bound always returns a valid insertion point, which may be past
    # the end or may point at a larger value. Both mean "not present".
    # The length check comes first so nums[first] never reads past the end.
    if first == len(nums) or nums[first] != target:
        return [-1, -1]             # -1, -1: the "absent" answer the problem asks for

    # The last target sits just before the first value greater than target.
    # + 1: integers, so target + 1 is the next value up.
    # - 1: step back from that first larger value onto the last target.
    last = lower_bound(nums, target + 1) - 1

    return [first, last]

Walkthrough

nums = [5, 7, 7, 8, 8, 10], target = 8. lower_bound(8) returns 3, the first index with a value at least 8. lower_bound(9) returns 5, the first index with a value at least 9, so the last 8 is at index 4. Answer [3, 4].

Now target = 6. lower_bound(6) returns 1, but nums[1] is 7, not 6, so the guard fires and the answer is [-1, -1]. That validation step is essential: a boundary search never tells you the value is present, only where it would go.

Reading the figure. Each row is one call to lower_bound. A cell shows T when nums[i] reaches the target, and green marks the first T. The run of 8s (amber) starts at the first boundary and ends one cell before the second.

The standard-library version

import bisect


def search_range_bisect(nums: list[int], target: int) -> list[int]:
    """What you would ship."""
    # bisect_left: first index with nums[i] >= target. Same as lower_bound.
    first = bisect.bisect_left(nums, target)
    # Past the end, or a different value there: target is absent.
    if first == len(nums) or nums[first] != target:
        return [-1, -1]             # -1, -1: the "absent" answer
    # bisect_right: first index with nums[i] > target.
    # - 1: step back onto the last copy of target.
    return [first, bisect.bisect_right(nums, target) - 1]

bisect_left is lower_bound and bisect_right is upper_bound. Knowing that these map onto the two boundary searches, and which is which, is worth stating.

Edge cases to raise

• Target absent but within the range of values: caught by the value check.
• Target larger than everything: first == len(nums), caught by the length check. That check must come first, or the index lookup raises.
• Every element equals the target: returns [0, n - 1].
• Empty array: lower_bound returns 0, which equals len(nums), so [-1, -1].
• Integer overflow on target + 1: not a concern in Python; in a fixed-width language write a separate upper_bound.

4. Peak Index in a Mountain Array Medium

Problem

An array is a mountain: it strictly increases to a single peak, then strictly decreases. Return the index of the peak, in O(log n).

Why binary search works with no sorted array

Solution

def peak_index_in_mountain_array(arr: list[int]) -> int:
    """Index of the single peak of a mountain array.

    Args:
        arr: Strictly increasing then strictly decreasing, length >= 3.

    Returns:
        The index i where arr[i] is the maximum.

    Example:
        >>> peak_index_in_mountain_array([0, 2, 5, 8, 4, 1])
        3
    """
    # 0 is the first index. len(arr) - 1 is the last. The peak is in between.
    left, right = 0, len(arr) - 1

    # Invariant: the peak is somewhere in [left, right].
    # < not <=: stop when one index is left, that index is the peak.
    while left < right:
        mid = left + (right - left) // 2    # // 2 rounds down, so mid < right

        # mid + 1 is safe: mid < right, so mid + 1 is at most right.
        # + 1 compares mid with its right neighbour to see the slope.
        if arr[mid] < arr[mid + 1]:
            left = mid + 1      # + 1: still climbing, so mid is not the peak
        else:
            right = mid         # descending or at the peak, so mid may be it

    return left                 # left == right, and that is the peak

Why right = mid and not mid - 1

When arr[mid] > arr[mid + 1], the array is already descending at mid, so mid itself might be the peak. Discarding it with mid - 1 would lose the answer. In the other branch, arr[mid] < arr[mid + 1] proves mid is not the peak, so mid + 1 is safe. Discard only what you have proved cannot be the answer. That sentence is the whole discipline of this pattern.

Note also that mid + 1 is always a valid index inside the loop: the guard is left < right, so mid < right ≤ n - 1. No bounds check is needed, and saying so shows you checked.

Walkthrough

arr = [0, 2, 5, 8, 4, 1]:

Reading the figure. The bars show the mountain. The F/T row is arr[i] > arr[i + 1], false while climbing and true going down. Blue is in range, amber is mid, red is discarded, green is the peak. On a climb the code drops mid. On a descent it keeps mid, since it might be the peak.

The generalisation: Find Peak Element

Edge cases to raise

• Minimum length 3, such as [0, 1, 0]: returns 1.
• Peak next to either end: [0, 5, 4, 3] or [1, 2, 3, 0].
• The problem guarantees a strict mountain, so no plateaus. With equal adjacent values the predicate stops being monotone and the approach fails. Ask.
• The loop uses left < right, not <=. With <= and right = mid it never terminates.