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

public static class BinarySearch
{
    /// <summary>Index of target in a sorted array of distinct integers, or -1.</summary>
    /// <param name="nums">Ascending, distinct integers.</param>
    /// <param name="target">The value to find.</param>
    /// <returns>The index of target, or -1 if it is not present.</returns>
    /// <example><c>Search([-1, 0, 3, 5, 9, 12], 9)</c> returns 4.</example>
    public static int Search(int[] nums, int target)
    {
        // Closed range. 0 is the first index. nums.Length - 1 is the last index.
        int left = 0, right = nums.Length - 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. Required in C#, where int wraps past 2^31 - 1.
            // / 2: integer midpoint, rounds down.
            int 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:

• left 0, right 5: mid 2, nums[2] = 3. Too big, so right = 1.
• left 0, right 1: mid 0, nums[0] = -1. Too small, so left = 1.
• left 1, right 1: mid 1, nums[1] = 0. Too small, so left = 2.
• left 2, right 1: left > right, so return -1.

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

public static class RotatedSearch
{
    /// <summary>Index of target in a rotated sorted array of distinct values, or -1.</summary>
    /// <param name="nums">A sorted array rotated at an unknown pivot. Values are distinct.</param>
    /// <param name="target">The value to find.</param>
    /// <returns>Its index, or -1.</returns>
    /// <example><c>Search([4, 5, 6, 7, 0, 1, 2], 0)</c> returns 4.</example>
    public static int Search(int[] nums, int target)
    {
        // Closed range. 0 is the first index. nums.Length - 1 is the last index.
        int left = 0, right = nums.Length - 1;

        // Invariant: if target is in nums, its index is inside [left, right].
        while (left <= right)
        {
            int 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 && 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 && 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:

• left 0, right 6: mid 3, nums[3] = 7. Left half is sorted, 4 to 7. 0 is not in [4, 7), so go right.
• left 4, right 6: mid 5, nums[5] = 1. Left half is sorted, 0 to 1. 0 is in [0, 1), so go left.
• left 4, right 4: mid 4, nums[4] = 0. Match, return 4.

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 LowerBound helper, called twice, answers both halves. For non-integer values you would write a matching UpperBound instead.

Solution

public static class SearchRange
{
    /// <summary>
    /// First index where nums[index] &gt;= target, or nums.Length if there is none.
    /// The predicate "nums[i] &gt;= target" is false then true, with one flip.
    /// </summary>
    /// <param name="nums">Ascending integers.</param>
    /// <param name="target">The bound. A long, so callers can pass int.MaxValue + 1L.</param>
    /// <returns>The insertion point for target.</returns>
    /// <example><c>LowerBound([5, 7, 7, 8, 8, 10], 8)</c> returns 3.</example>
    public static int LowerBound(int[] nums, long target)
    {
        // Half-open [left, right). 0 is the first index. right = nums.Length is one
        // past the end, so "every value is smaller" can return nums.Length.
        int left = 0, right = nums.Length;

        // Invariant: nums[..left] are all < target. nums[right..] are all >= target.
        while (left < right)
        {
            int 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
    }

    /// <summary>First and last index of target in a sorted array, or [-1, -1].</summary>
    /// <param name="nums">Ascending integers, duplicates allowed.</param>
    /// <param name="target">The value to locate.</param>
    /// <returns>[firstIndex, lastIndex], or [-1, -1] if target is absent.</returns>
    /// <example><c>Find([5, 7, 7, 8, 8, 10], 8)</c> returns [3, 4].</example>
    public static int[] Find(int[] nums, int target)
    {
        int first = LowerBound(nums, target);

        // LowerBound 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 == nums.Length || 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.
        // + 1L: the next integer up, done in long so int.MaxValue + 1 cannot wrap.
        // - 1: step back from that first larger value onto the last target.
        int last = LowerBound(nums, target + 1L) - 1;

        return [first, last];
    }
}

Walkthrough

nums = [5, 7, 7, 8, 8, 10], target = 8. LowerBound(8) returns 3, the first index with a value at least 8. LowerBound(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. LowerBound(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 LowerBound. 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

public static class SearchRangeBcl
{
    // Never returns 0, so BinarySearch never stops on an equal value. It keeps going
    // left on ties and ends at the complement (~) of the first index >= value.
    // -1 = "element is smaller, go right". 1 = "element is bigger or equal, go left".
    private static readonly Comparer<int> Lower = Comparer<int>.Create((a, b) => a < b ? -1 : 1);
    // Same trick, but ties go right: ends at ~ of the first index > value.
    private static readonly Comparer<int> Upper = Comparer<int>.Create((a, b) => a <= b ? -1 : 1);

    /// <summary>
    /// What you would ship: Array.BinarySearch with a comparer that never says "equal",
    /// which turns it into a lower bound and an upper bound.
    /// </summary>
    /// <param name="nums">Ascending integers, duplicates allowed.</param>
    /// <param name="target">The value to locate.</param>
    /// <returns>[firstIndex, lastIndex], or [-1, -1] if target is absent.</returns>
    /// <example><c>Find([5, 7, 7, 8, 8, 10], 8)</c> returns [3, 4].</example>
    public static int[] Find(int[] nums, int target)
    {
        // ~ undoes the complement. The search never "finds", so the result is always < 0.
        int first = ~Array.BinarySearch(nums, target, Lower);
        // Past the end, or a different value there: target is absent.
        if (first == nums.Length || nums[first] != target)
        {
            return [-1, -1];            // -1, -1: the "absent" answer
        }
        // Upper: first index with nums[i] > target.
        // - 1: step back onto the last copy of target.
        int last = ~Array.BinarySearch(nums, target, Upper) - 1;
        return [first, last];
    }
}

The comparer never returns 0, so Array.BinarySearch never stops on a match. On ties, Lower says “go left” and Upper says “go right”. The search runs off the end of the range and returns the complement of the boundary. Lower gives the lower bound, the first index with a value at least target. Upper gives the upper bound, the first index with a value greater than target. Knowing which is which is worth stating. It is clever, so in an interview write LowerBound by hand first and offer this second.

Edge cases to raise

• Target absent but within the range of values: caught by the value check.
• Target larger than everything: first == nums.Length, caught by the length check. That check must come first, or nums[first] throws IndexOutOfRangeException.
• Every element equals the target: returns [0, n - 1].
• Empty array: LowerBound returns 0, which equals nums.Length, so [-1, -1].
• Integer overflow on target + 1: real in C#. With target = int.MaxValue an int sum wraps to int.MinValue. The code passes target + 1L, a long, so it cannot wrap. Writing a separate UpperBound also works.

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

public static class MountainPeak
{
    /// <summary>Index of the single peak of a mountain array.</summary>
    /// <param name="arr">Strictly increasing then strictly decreasing, length &gt;= 3.</param>
    /// <returns>The index i where arr[i] is the maximum.</returns>
    /// <example><c>PeakIndex([0, 2, 5, 8, 4, 1])</c> returns 3.</example>
    public static int PeakIndex(int[] arr)
    {
        // 0 is the first index. arr.Length - 1 is the last. The peak is in between.
        int left = 0, right = arr.Length - 1;

        // Invariant: the peak is somewhere in [left, right].
        // < not <=: stop when one index is left, that index is the peak.
        while (left < right)
        {
            int 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]:

• left 0, right 5: mid 2. 5 < 8, climbing, so left = 3.
• left 3, right 5: mid 4. 4 > 1, descending, so right = 4.
• left 3, right 4: mid 3. 8 > 4, descending, so right = 3.
• left 3, right 3: the loop ends. Return 3.

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.