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
    """
    left, right = 0, len(nums) - 1

    # Invariant: if target is in nums, its index is inside [left, right].
    while left <= right:
        # Overflow-safe form. Identical in Python, required in C++ or Java.
        mid = left + (right - left) // 2

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

    return -1

Walkthrough

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

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
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            # Left half [left, mid] is sorted, so its range is known exactly.
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Then the right half [mid, right] must be the sorted one.
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

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

Walkthrough

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

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.
    """
    left, right = 0, len(nums)        # half-open: right is one past the end

    while left < right:
        mid = left + (right - left) // 2

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

    return left


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".
    if first == len(nums) or nums[first] != target:
        return [-1, -1]

    # The last target sits just before the first value greater than 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.

The standard-library version

import bisect


def search_range_bisect(nums: list[int], target: int) -> list[int]:
    """What you would ship."""
    first = bisect.bisect_left(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    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
    """
    left, right = 0, len(arr) - 1

    # Invariant: the peak is somewhere in [left, right].
    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] < arr[mid + 1]:
            left = mid + 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]:

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.