Binary search and variations: lower bound, rotated array, answer search

1. Overview

Binary search is a search algorithm on sorted data with O(log n) complexity. The idea is simple, but the implementation is easy to get wrong: infinite loops, off-by-one errors, integer overflow when computing mid.

This article goes from the basic version to common variations: finding the first/last position of a duplicate element, counting occurrences, searching in a rotated array, and answer search binary search. After reading, you’ll have a set of error-resistant implementation patterns with tests to verify them.

2. Basic binary search

Suppose you have an array of product prices sorted in increasing order and need to find the position of a target price:

public final class PriceSearch {

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

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

Explanation:

• lo and hi form a closed interval [lo, hi]. This is the region where target might be.
• The condition lo <= hi means the loop continues as long as the interval contains at least one element.
• mid = lo + (hi - lo) / 2 avoids overflow. Writing (lo + hi) / 2 overflows when lo + hi exceeds Integer.MAX_VALUE. An equivalent approach is (lo + hi) >>> 1.
• After each step, we exclude mid from the interval (mid + 1 or mid - 1), so the interval always shrinks and the loop is guaranteed to terminate.

Result:

3
-1

This version works when the array has no duplicates and you only need to know “found or not”. With duplicates, it returns some position in the duplicate group. Usually that’s not what you want.

3. Lower bound and upper bound

The two most important variations are:

• lower bound: the first index where a[i] >= target.
• upper bound: the first index where a[i] > target.

Both always return an index in [0, n], even if target is not in the array. This index is the insertion position that maintains the sorted order.

public final class Bounds {

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

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Differences from the basic version:

• We use a half-open interval [lo, hi), so hi is initialized to a.length and the loop condition is lo < hi.
• When a[mid] satisfies the condition ‘is already large enough’, we assign hi = mid instead of mid - 1, because mid could still be the answer.
• The two functions differ only in the < and <= operators.

Try with an array containing duplicates:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

With 300, the result 4 tells us that inserting 300 would place it before 350. With 900, the result equals n, meaning all elements are smaller.

3.1. First position, last position, and count

From these two functions, you can immediately derive common problems:

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

With the prices above and target = 200, we get firstIndexOf = 1, lastIndexOf = 3, count = 3. Key point: always check bounds i < a.length (or i >= 0) before reading a[i].

3.2. Count elements in a range

A practical application is counting orders with value in [min, max]:

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

With {100, 200, 200, 200, 350, 500} and range [150, 400], let’s calculate: upperBound(400) = 5, lowerBound(150) = 1, so the result is 4. Each query costs only O(log n), no need to scan the entire array.

4. Search in rotated array

A rotated array is a sorted array that is ‘cut’ at a point and its two halves are swapped, for example {40, 50, 60, 10, 20, 30}. The array is no longer increasing throughout, but at least one half around mid still has order. We use that to decide which direction to go:

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // left half is sorted
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // right half is sorted
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

Explanation:

• a[lo] <= a[mid] tells us the interval [lo, mid] is increasing. If target falls within the value range of this interval, we narrow towards the left. Otherwise, we go right.
• Otherwise, the interval [mid, hi] is increasing, and we reason symmetrically.

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

Note: This implementation assumes the array has no duplicates. With an array like {2, 2, 2, 3, 2}, the condition a[lo] <= a[mid] can no longer distinguish which half is sorted. In that case, you must handle the additional a[lo] == a[mid] case by incrementing lo, and worst-case complexity becomes O(n).

5. Binary search on the answer

This is the most powerful variation. It does not search an array but finds the smallest value satisfying a condition. The only requirement to apply it is that the predicate must be monotonic: if x satisfies it, then all values larger than x also satisfy it. In other words, the sequence of results has the form false, false, ..., true, true.

We write a general function:

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** The smallest value in [lo, hi] for which ok returns true. Assumes ok(hi) == true. */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

This function has the same structure as lowerBound. In fact, lowerBound is just a special case with the predicate a[i] >= target.

Applying to a real problem: a warehouse has packages in a fixed order that must be delivered within maxDays days. Each day a truck carries consecutive packages, with total weight not exceeding the truck’s capacity. What is the minimum required capacity?

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

Explanation:

• lo is the heaviest package, since the truck must carry at least one package. hi is the total weight, since then only one day is needed. Thus ok(hi) is definitely true.
• canShip simulates a greedy approach: load packages onto the truck until it exceeds capacity, then move to the next day. Higher capacity means fewer days, so the predicate is monotonic.
• Total cost is O(n · log(sum)), rather than trying each capacity.

6

With capacity 6, the delivery schedule is [3, 2], [2, 4], [1, 4], exactly 3 days. With capacity 5, we need 4 days, so 5 doesn’t work.

Using this pattern, you can solve many other problems: minimum threads to process a batch on time, smallest rate limit, integer square root of a number.

6. Using Java’s standard library

Java already has Arrays.binarySearch and Collections.binarySearch. You need to understand their return values:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• When found, the function returns the index of the element.
• When not found, it returns -(insertionPoint) - 1. Here the insertion point is 4, so the result is -5. To recover the insertion point, calculate -(result) - 1.
• With duplicates, the documentation does not guarantee which position in the duplicate group is returned. If you need the first or last position, use custom lowerBound/upperBound.

With a list of objects, you pass a Comparator matching the sorted order:

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

Note: Collections.binarySearch on LinkedList does not achieve O(log n) because index access costs O(n). Use ArrayList or arrays.

7. Testing

Add JUnit 5 and AssertJ dependencies. If your project uses spring-boot-starter-test, both are already included.

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

Write tests for edge cases. This is where binary search is most likely to break:

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

The lowerBoundMatchesLinearScan test compares against linear counting on 1,000 random arrays, including empty arrays. This kind of differential testing catches off-by-one errors much better than a few hand-written examples.

8. Common pitfalls and when not to use

Common errors:

• Mixing interval conventions. You initialize hi = n (half-open) but loop with while (lo <= hi) and assign hi = mid - 1. This reads outside the array. Choose one convention and stick with it.
• Infinite loops. If you write lo = mid with mid = (lo + hi) / 2, when hi = lo + 1 then mid == lo and the interval doesn’t shrink. If you really need lo = mid, round up: mid = lo + (hi - lo + 1) / 2.
• Overflow when computing mid or when computing sums in answer search. Use long for potentially large values.
• Non-monotonic predicate. Binary search still returns a number, but that number is meaningless. Prove monotonicity before applying it.

When not to use binary search:

• Data is unsorted and you only search a few times. Sorting costs O(n log n), while linear search costs O(n).
• You only need to check ‘found or not’ with many queries. In that case, HashSet gives O(1) average.
• Data changes frequently with many insertions and deletions. Keeping the array sorted costs O(n) per insertion. Consider TreeMap/TreeSet, which have ceilingKey, floorKey, higherKey equivalent to lower bound and upper bound.
• The array is very small, just tens of elements. Linear scan is often as fast or faster thanks to cache, and the code is simpler.

9. Conclusion

Binary search is not just ‘finding an element in an array’. When you master lower bound and upper bound with the half-open interval [lo, hi), you can solve problems of first/last position, counting elements, and range counting in just a few lines. A rotated array requires an additional step to identify which half is sorted. Answer search binary search extends the technique to any problem with a monotonic predicate.

Stick to a single interval convention, use >>> or lo + (hi - lo) / 2 to avoid overflow, and always have tests comparing against linear search. These three habits eliminate nearly all the errors that binary search is notorious for.