Algorithms - Binary Search - Searching in sorted/monotonic spaces

Published Mar 11, 2026

Posted in
programming
question
.net
c#

Intro

At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

Efficient prefix and pattern matching - solved by Trie and KMP String Search
Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I will be covering Binary Search, used to efficiently search sorted arrays or otherwise monotonic spaces.

When to use Binary Search

You already know classic binary search on a sorted array. But the real power shows up when the array is not obviously sorted, or when there is no array at all - only a monotonic (always increasing or always decreasing) decision space.

Classic signs:

The array is sorted but rotated / shifted
You need to find the minimum / maximum in a rotated sorted array
You're searching for the boundary between two behaviors (first true / last false)
You want the minimal / maximal value that satisfies some condition
The answer lies in a large but monotonic range (0 to 10⁹, days, capacity, speed, etc.)
Linear search would be too slow, but the property lets you discard half the search space every step

One-sentence rule: Whenever you can define a monotonic predicate "is it possible / good enough at value X?" and the answer changes only once (from false to true or viceversa), binary search on the answer range will usually give you O(log N) time instead of O(N).

Classic Binary Search Template

I know that C# already has a method called Array.BinarySearch , but the problems you're going to get usually have a little quirk that forces you to implement it manually, like the array is sorted, then rotated. But it's really easy.

Use this pattern - it avoids off-by-one errors and integer overflow:

int BinarySearchLeftMost(int[] arr, int target)
{
    int left = 0;
    // note: one past the end
    int right = arr.Length;           

    while (left < right)
    {
        // same as (left+right)/2, but avoiding overflows
        int mid = left + (right - left) / 2;

        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }

    return left;   // insertion point or first >= target
}

Just remember:

left < right loop
mid = left + (right - left)/2 prevents overflow
When condition is true, shrink right
When false, shrink left
At the end left is usually the boundary you want
You may choose to use a simpler search algorithm when the size of the search is small enough

Example – Search in Rotated Sorted Array

Problem statement: You are given a sorted array that has been rotated an unknown number of times. Find the index of target or return -1.

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

Here is the solution:

int Search(int[] nums, int target)
{
    var left = 0;
    var right = nums.Length - 1;

    while (left <= right)
    {
        var mid = left + (right - left) / 2;

        if (nums[mid] == target) return mid;

        // Left half is sorted
        if (nums[left] <= nums[mid])
        {
            if (nums[left] <= target && target < nums[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        // Right half is sorted
        else
        {
            if (nums[mid] < target && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
        }
    }

    return -1;
}

int[] nums = [4, 5, 6, 7, 0, 1, 2];
var target = 0;
Console.WriteLine(Search(nums, target)); //4

It's silly, really. You just have an extra if/then block to figure out which of the halves is the unrotated one. Other than that it's a classic binary search.

Complexity goes from O(n) (the naive linear scan) to O(log n) for the binary search.

Example - Capacity to ship packages within D days

The problem is called Binary Search on Answer (Capacity To Ship Packages Within D Days).

Problem statement: Given weights of packages and D days, find the minimal ship capacity needed to ship all packages in D days.

Solution:

int ShipWithinDays(int[] weights, int days)
{
    // at least the heaviest package
    var left = weights.Max();
    // at most everything in one day
    var right = weights.Sum();

    while (left < right)
    {
        var mid = left + (right - left) / 2;

        if (CanShip(weights, mid, days))
        {
            // try smaller capacity
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }

    return left;
}

bool CanShip(int[] weights, int capacity, int days)
{
    var current = 0;
    var neededDays = 1;

    foreach (var w in weights)
    {
        var newCurrent = current + w;
        if (newCurrent > capacity)
        {
            neededDays++;
            current = w;
            if (neededDays > days) return false;
        }
        else
        {
            current = newCurrent;
        }
    }
    return true;
}
Console.WriteLine(ShipWithinDays([1, 3, 45, 6, 4, 32, 24, 5, 6, 32], 4)); //49

Step-by-step checklist to recognize monotonicity in the example above:

What are we actually searching for?
- We are searching for the smallest possible ship capacity (let's call it C) such that it is still possible to ship all packages in ≤ days days.
Define the clear yes/no question (the predicate): Is it possible to ship all packages using capacity ≤ C within ≤ days days?
- We call this predicate CanShip(C, weights, days)
- It returns true or false
Ask the crucial monotonicity question: If CanShip(C) is true, what happens when we increase C to C+1, C+2, etc.?
- Answer: If you could already ship everything with capacity C, then you can definitely ship everything with any larger capacity (C+1, C+10, C+1000, ...).
- In other words: larger capacity can only make the problem easier or keep it equally easy - never harder.
- Formally: If CanShip(C) == true, then CanShip(C') == true for all C' > C
- The opposite is also true: If CanShip(C) == false, then CanShip(C') == false for all C' < C
Conclusion from the above:
- The predicate CanShip(C) is monotonic non-decreasing with respect to C.
- There exists some threshold value C_min such that:
  - for all C < C_min, meaning CanShip(C) = false
  - for all C ≥ C_min, meaning CanShip(C) = true
- This is the classic "staircase" / "boundary" shape that binary search loves.

Visual intuition

Capacity:

false false false true true true true

↑

the minimal valid capacity we want

Whenever increasing the search variable (capacity, speed, height, number of bananas per hour, pages per day, etc.) can only help (never hurt) the feasibility, then the feasibility function is monotonic, so binary search applies.

Ask yourself these two questions:

"If I make the constraint looser (bigger capacity, more days, higher speed limit, etc.), does the answer become easier or stay the same?
"If I make the constraint stricter (smaller capacity, fewer days, lower speed, etc.), does the answer become harder or stay the same?

If both answers are yes the feasibility is monotonic, therefore binary search on the answer is applicable.

Counter example: "find a number in an unsorted array" - increasing the search range doesn't consistently help or hurt. One must use linear scan or hash set, not binary search.

So in short: you know Example 2 is monotonic because making the ship capacity larger can only help (never hurt) the ability to finish in D days and that consistent direction creates the perfect binary-search-friendly boundary.

Example - Consistent hashing

Advanced Application: Consistent Hashing. Binary search shines on any sorted structure, not just arrays. One of the most elegant real-world uses is consistent hashing, the algorithm that powers load balancers, distributed caches, and databases like Cassandra and DynamoDB.

Use it when you are distributing keys (users, requests, cache entries) across a changing set of servers. Traditional hashing (key % numServers) forces every key to be remapped whenever a server is added or removed. Consistent hashing limits the damage to roughly 1/N of the keys.

Imagine a clock (the "ring") with numbers from -∞ to +∞.

Each server gets many "virtual nodes" placed on the ring (via hash(server + replica)).
The virtual nodes are kept sorted.
To find where a key goes: hash the key (binary search for the first virtual node clockwise - the next larger hash, or wrap to the beginning).
When a server is added/removed, only the keys between its old and new neighbors move.

We implement the ring with a List<long> (kept sorted) and BinarySearch, exactly the technique covered in this post.

Here is the solution:

var chr = new ConsistentHashRing();

chr.AddServer("server1");
chr.AddServer("server2");
chr.AddServer("server3");

Console.WriteLine("Before removal:");
Console.WriteLine($"key1   -> {chr.GetServerForKey("key1")}");
Console.WriteLine($"user42 -> {chr.GetServerForKey("user42")}");
Console.WriteLine($"cacheX -> {chr.GetServerForKey("cacheX")}");

chr.RemoveServer("server2");   // only ~1/3 of keys will move

Console.WriteLine("\nAfter removing server2:");
Console.WriteLine($"key1   -> {chr.GetServerForKey("key1")}");
Console.WriteLine($"user42 -> {chr.GetServerForKey("user42")}");
Console.WriteLine($"cacheX -> {chr.GetServerForKey("cacheX")}");

public class ConsistentHashRing
{
    private readonly List<long> ring = [];
    private readonly Dictionary<long, string> hashToServer = [];
    private readonly Dictionary<string, List<long>> serverToHashes = [];
    private const int VirtualNodesPerServer = 100; // increase for better distribution

    private long Hash(string key)
    {
        return Math.Abs(key.GetHashCode());
    }

    public void AddServer(string server)
    {
        if (serverToHashes.ContainsKey(server)) return;

        var hashes = new List<long>(VirtualNodesPerServer);
        for (int i = 0; i < VirtualNodesPerServer; i++)
        {
            long hash = Hash(server + "#" + i);

            int idx = ring.BinarySearch(hash);
            if (idx < 0) idx = ~idx;

            ring.Insert(idx, hash);
            hashToServer[hash] = server;
            hashes.Add(hash);
        }
        serverToHashes[server] = hashes;
    }

    public void RemoveServer(string server)
    {
        if (!serverToHashes.TryGetValue(server, out var hashes)) return;

        foreach (var hash in hashes)
        {
            int idx = ring.BinarySearch(hash);
            if (idx >= 0)
            {
                ring.RemoveAt(idx);
                hashToServer.Remove(hash);
            }
        }
        serverToHashes.Remove(server);
    }

    public string GetServerForKey(string key)
    {
        if (ring.Count == 0) return null;

        long hash = Hash(key);

        int idx = ring.BinarySearch(hash);
        if (idx < 0) idx = ~idx;
        if (idx == ring.Count) idx = 0; // wrap around the ring

        return hashToServer[ring[idx]];
    }
}

GetServerForKey does exactly one BinarySearch on the sorted list of virtual node hashes.

If the key hash lands exactly on a node then use it.
Otherwise ~idx gives the insertion point, i.e. the next server clockwise.
The wrap-around (if idx == Count) makes the ring circular.

That's O(log (N * replicas)) lookup, blazing fast even with thousands of virtual nodes.

Complexity:

Lookup (GetServerForKey): O(log (N * replicas)) thanks to BinarySearch
Add/Remove server: O(replicas * log (N * replicas)) (insert/delete in the list)

In practice N is small (10–1000 servers) and add/remove is rare, so it’s perfect.

Real-world notes:

Cassandra, DynamoDB, Redis Cluster, and most CDNs use this exact pattern.
In production replace the simple Hash with MD5, MurmurHash3, or SHA-1.
Virtual nodes (the 100 replicas) make distribution even - without them some servers would get way more keys than others.

Conclusion

Advanced binary search is one of the most powerful patterns in coding interviews. Once you see a monotonic property or decision boundary, you can often turn a brute-force O(n) or worse solution into O(log n) or O(n log n) with very little code.