Optimizing Hot Paths: Advanced Binary Search in Java

Well, I have to confess – I spent last Tuesday staring at a flame graph that made absolutely no sense. We had a microservice responsible for querying historical pricing data, nothing fancy, just an in-memory cache of the last 24 hours of ticks, and the CPU usage was pinned at 90%.

Actually, the culprit? A well-intentioned stream().filter().findFirst() inside a tight loop. (I love the Stream API, it made Java readable again, but when you’re dealing with 500,000 objects in a list that is already sorted – or mostly sorted – doing a linear scan is just burning money. We were processing 10,000 requests per second, and that linear scan was adding 40ms of latency per call. It adds up.)

The fix wasn’t just “use Collections.binarySearch.” Our data structure was a circular buffer (to keep memory usage constant), effectively making it a Rotated Sorted Array. Standard libraries choke on that. I had to roll up my sleeves and write some actual algorithms.

The Circular Buffer Problem

In high-frequency systems, you often write data to a fixed-size array that loops back to the start when full. It’s efficient for memory, but it breaks the contract of a standard binary search because the elements aren’t strictly increasing from index 0 to N. They go up, drop off a cliff, and go up again.

But I ended up writing a generic utility class that handles this. I made it work with any Comparable type because, honestly, I didn’t want to rewrite this logic for timestamps, prices, and sequence IDs separately.

public class CircularSearchUtils {

    /**
     * Finds an element in a rotated sorted list.
     * Time Complexity: O(log n)
     */
    public static <T extends Comparable<T>> int searchRotated(List<T> list, T target) {
        // Code block omitted for brevity
    }
}

Handling Duplicates: First and Last Occurrence

The rotated array was problem number one. Problem number two was fetching ranges. Often, business logic isn’t “does this exist?” but “give me all events that happened at timestamp X.” Since timestamps aren’t unique, a standard binary search might land in the middle of a cluster of identical values. You don’t know if it’s the first one, the last one, or the 50th one.

To fix this, I encapsulated the logic to find the first and last occurrence in a reusable BoundarySearch class.

public class BoundarySearch {

    public static <T extends Comparable<T>> int findFirstOccurrence(List<T> list, T target) {
        // Code block omitted for brevity
    }

    public static <T extends Comparable<T>> int findLastOccurrence(List<T> list, T target) {
        // Code block omitted for brevity
    }
}

Integrating with Streams (The Right Way)

I’m not saying “never use Streams.” I’m saying “don’t use Streams for the search.” Use the algorithm for the search, then use Streams for the transformation. This approach is better than relying on unreadable Streams.

public List<String> getTransactionIdsForPrice(List<Transaction> sortedTransactions, double price) {
    // Transaction implements Comparable<Transaction> based on price
    Transaction dummyTarget = new Transaction(price); 
    
    int first = BoundarySearch.findFirstOccurrence(sortedTransactions, dummyTarget);
    int last = BoundarySearch.findLastOccurrence(sortedTransactions, dummyTarget);

    if (first == -1) {
        return List.of();
    }

    // Efficient sub-list view, then stream
    return sortedTransactions.subList(first, last + 1)
            .stream()
            .map(Transaction::getId)
            .toList(); // Java 16+ syntax
}

Real-World Performance Check

I ran a quick benchmark on this setup. We populated a ArrayList with 10 million generic objects. The goal was to find a specific range of 50 items in the middle.

• Stream Filter: 145ms (Average over 100 runs)
• Custom Binary Search: 0.04ms (Average over 100 runs)

The stream version has to touch every single element until it finishes or you use short-circuiting (which is hard when you want a range). The binary search touches maybe 20 elements. It’s not even a contest. As mentioned in Stop Writing Legacy Java: A 2025 Survival Guide, understanding algorithms is key to writing high-performance Java code.

Final Thoughts

It’s easy to rely on the standard library for everything. And 99% of the time, you should. But when you are hitting scaling limits, understanding the underlying data structures—like how to navigate a rotated array or efficient range finding—is what separates a “Java Developer” from a “Backend Engineer.” As discussed in Java Collections: You’re Probably Using Them Wrong, mastering data structures and algorithms is crucial for writing high-performance Java applications.

Next time you see a stream().filter() on a large, sorted dataset, do your CPU a favor. Write the search logic.