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.
FAQ
How do you perform binary search on a rotated sorted array in Java?
A standard Collections.binarySearch fails on rotated sorted arrays because elements aren’t strictly increasing from index 0 to N. The article demonstrates a generic CircularSearchUtils utility class with a searchRotated method accepting any Comparable type, achieving O(log n) time complexity. This handles circular buffers common in high-frequency systems, where fixed-size arrays loop back to the start and break the contract of a traditional binary search.
Why is stream().filter().findFirst() slow on large sorted lists in Java?
Stream filter operations perform a linear scan, touching every element until a match is found, which wastes CPU on sorted data. In the article’s benchmark with 10 million objects, Stream Filter averaged 145ms while custom binary search took just 0.04ms. In a production microservice processing 10,000 requests per second against 500,000 sorted objects, this linear scan added 40ms of latency per call.
How do you find the first and last occurrence of a duplicate value using binary search?
The article presents a reusable BoundarySearch class with findFirstOccurrence and findLastOccurrence methods that accept any Comparable type. This solves the problem where standard binary search lands in the middle of a cluster of identical values without knowing its position. It’s useful for range queries like fetching all events at a specific timestamp, where timestamps aren’t unique across records.
Should you use Streams or binary search for querying sorted data in Java?
Use binary search for the lookup, then Streams for transformation. The article recommends calling BoundarySearch to find first and last indices, extracting a subList view of the matching range, then streaming that smaller slice to map results. This avoids touching every element while preserving readable Stream syntax for mapping operations like extracting transaction IDs with Transaction::getId and toList().