Binary Search LeetCode Problems Explained in C#

2025-08-08

Binary search is the quiet workhorse of coding interviews. You can solve far more than “find a number in a sorted array.” Once you learn a few reusable patterns, you will crush a big slice of LeetCode with clean, fast C# code.

Below I will give you a practical toolkit: core template, boundary variants, and the most common problem patterns you will face.

The core idea in one minute

Binary search cuts the search space in half each step.

Use it when:

The input is sorted or can be treated as sorted
Or the answer lies on a monotonic condition
Or you can check “good vs bad” with a predicate

Time is O(log n) and space is O(1) for array problems.

C# template you can memorize

This version avoids infinite loops and off by one errors.

public static int BinarySearch(int[] a, int target) {
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1; // not found
}

Key checks:

Use lo + (hi - lo) / 2 to avoid overflow
Loop while lo <= hi
Move lo to mid + 1 or hi to mid - 1

Variant 1: First occurrence (lower bound)

Find the first index where a[i] >= target. Returns a.Length if all elements are smaller. Useful for “search insert position” and dedup boundaries.

public static int LowerBound(int[] a, int target) {
    int lo = 0, hi = a.Length; // half open [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Variant 2: Last occurrence (upper bound minus one)

Find the last index where a[i] <= target.

public static int UpperBoundMinusOne(int[] a, int target) {
    int lo = 0, hi = a.Length; // [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo - 1; // last <= target
}

Pattern A: Search Insert Position

Return the index to insert target into a sorted array.

public static int SearchInsert(int[] a, int target) {
    return LowerBound(a, target);
}

Reasoning: the first index with value not smaller than target is exactly where it belongs.

Pattern B: First Bad Version style problems

You are given a monotonic predicate IsGood(x) which flips from false to true at some point. Find the first index that makes it true. Classic “first true.”

public static int FirstTrue(int n, Func<int, bool> isTrue) {
    int lo = 1, hi = n; // or 0 based if needed
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isTrue(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo; // smallest index with isTrue == true
}

Use cases: capacity checks, time needed, minimum speed, smallest radius.

Pattern C: Peak Element

Find an index i where a[i] > a[i - 1] and a[i] > a[i + 1]. There is always at least one peak.

public static int FindPeakElement(int[] a) {
    int lo = 0, hi = a.Length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < a[mid + 1]) lo = mid + 1; // climb right
        else hi = mid; // peak is mid or left
    }
    return lo;
}

Pattern D: Rotated Sorted Array search

Array was sorted then rotated. Find target in O(log n).

public static int SearchRotated(int[] a, int target) {
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;

        // left half sorted
        if (a[lo] <= a[mid]) {
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else { // right half sorted
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Pattern E: Binary search on the answer

When the search space is not the array indices but a numeric answer range. You need a check that is monotonic in the candidate answer.

Example: Koko Eating Bananas

Given piles and hours h, find the minimum eating speed k so she finishes in h hours. The faster you eat, the fewer hours, which is monotonic.

public static int MinEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    foreach (var p in piles) hi = Math.Max(hi, p);

    bool CanFinish(int k) {
        long hours = 0;
        foreach (var p in piles) {
            hours += (p + k - 1) / k; // ceil(p / k)
            if (hours > h) return false;
        }
        return hours <= h;
    }

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (CanFinish(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Other “search on answer” favorites

Minimum capacity to ship packages within D days
Split array largest sum
Minimum time to make m bouquets
Allocate minimum number of pages

If you can write a Can(mid) that says yes or no and it becomes easier as mid grows or shrinks, you can likely binary search it.

Pattern F: Count occurrences with bounds

Count how many times target appears in a sorted array using lower and upper bounds.

public static int CountEqual(int[] a, int target) {
    int left = LowerBound(a, target);
    int right = LowerBound(a, target + 1);
    return Math.Max(0, right - left);
}

Common pitfalls

Midpoint overflow on very large ranges. Use lo + (hi - lo) / 2.
Wrong loop condition. If you use [lo, hi) use while (lo < hi). If you use [lo, hi] use while (lo <= hi). Be consistent.
Infinite loops when mid does not make progress. Always move lo or hi off mid.
Off by one in lower or upper bound. Write down the invariant for your interval type.
Mixing 0 based and 1 based indexing. Pick one and stick to it.

Fast practice checklist

Can I express this as first true or last false
Is the array sorted or can I treat the search space as monotonic
Which interval type fits best [lo, hi] or [lo, hi)
What is the exact invariant at each loop
What is the proof that the loop terminates

Tiny NUnit test sketch

using NUnit.Framework;

public class BinarySearchTests {
    [Test]
    public void LowerBound_Works() {
        int[] a = {1, 3, 3, 5, 8};
        Assert.AreEqual(1, LowerBound(a, 3));
        Assert.AreEqual(3, LowerBound(a, 5));
        Assert.AreEqual(5, LowerBound(a, 10));
    }

    [Test]
    public void SearchRotated_FindsTarget() {
        int[] a = {4,5,6,7,0,1,2};
        Assert.AreEqual(4, SearchRotated(a, 0));
        Assert.AreEqual(-1, SearchRotated(a, 3));
    }
}

Drop these next to your solutions to lock in correctness.

Wrap up

Binary search is bigger than a one liner. Once you master lower bound, upper bound, rotated arrays, peaks, and search on answer, you will start seeing the same structure in many problems.

If you want a quick way to sanity check your approach during practice, you can use a helper that captures the prompt and shows a clean solution with the reasoning you can explain back. It keeps you moving instead of getting stuck.

Try StealthCoder when you want an instant outline and code to study while practicing: https://stealthcoder.app