Java Searching Algorithms
Searching is the process of finding whether a particular value exists in a collection of data, and if so, where it is located. Almost every program you write eventually needs to look something up — a username in a list, a product ID in an inventory, a target score in an array of results. Java gives you the building blocks to implement searching yourself, and understanding how the two classic algorithms — linear search and binary search — actually work will make you a far better programmer, because these ideas underpin databases, hash maps, and countless real-world systems.
Overview: How Searching Algorithms Work
Linear search (also called sequential search) is the simplest possible approach: start at the first element and check every element, one by one, until you find the target or run out of elements. It makes no assumptions about the data — the array can be sorted or unsorted, it doesn’t matter. Its cost grows directly with the size of the input: in the worst case (the target is the last element, or isn’t there at all), it examines every single element. This is called O(n) time complexity, where n is the number of elements.
Binary search is dramatically faster, but it comes with a strict requirement: the data must already be sorted. Binary search works the way you’d look up a word in a paper dictionary: instead of reading every page from the start, you open to the middle, decide whether your word comes before or after that point, and repeat the process on the correct half. Each comparison eliminates half of the remaining elements, so binary search runs in O(log n) time. For an array of 1,000,000 elements, linear search might need up to a million comparisons, while binary search needs at most about 20.
Under the hood, both algorithms operate directly on the array stored in memory. Java arrays are contiguous blocks of memory, so accessing any index (like arr[mid]) is an O(1) operation — the JVM computes the memory address directly from the base address and the index, with no traversal needed. This is precisely what makes binary search’s “jump to the middle” strategy possible; a linked list, which lacks random access, cannot support true binary search efficiently.
Comparing the Two
| Aspect | Linear Search | Binary Search |
|---|---|---|
| Requires sorted data | No | Yes |
| Best case | O(1) | O(1) |
| Worst case | O(n) | O(log n) |
| Works on | Arrays, lists, any iterable | Arrays/lists with random access |
| Implementation | Very simple | Slightly trickier (index math) |
Syntax
Linear search follows this general shape:
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
// found at index i
}
}Binary search follows this general shape, using two pointers that shrink the search range:
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == target) {
// found at index mid
} else if (array[mid] < target) {
low = mid + 1; // search the right half
} else {
high = mid - 1; // search the left half
}
}lowandhigh— the current boundaries of the range still being searched.mid— the midpoint index, recalculated every iteration.- The loop continues while
low <= high; once they cross, the range is empty and the target is not present. - Comparing
array[mid]totargettells you which half to keep searching.
Examples
Example 1: Linear Search
public class Main {
public static void main(String[] args) {
int[] numbers = {34, 12, 78, 5, 90, 23, 67};
int target = 90;
int index = -1;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == target) {
index = i;
break;
}
}
if (index != -1) {
System.out.println("Found " + target + " at index " + index);
} else {
System.out.println(target + " not found");
}
}
}Output:
Found 90 at index 4The loop checks each element in order — 34, 12, 78, 5, then 90 — and stops as soon as it finds a match, recording the index and breaking out early. Notice the array is completely unsorted; linear search doesn’t care about order at all.
Example 2: Binary Search (Iterative)
public class Main {
public static void main(String[] args) {
int[] sortedNumbers = {5, 12, 23, 34, 67, 78, 90};
int target = 67;
int low = 0;
int high = sortedNumbers.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (sortedNumbers[mid] == target) {
result = mid;
break;
} else if (sortedNumbers[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (result != -1) {
System.out.println("Found " + target + " at index " + result);
} else {
System.out.println(target + " not found");
}
}
}Output:
Found 67 at index 4This time the array is sorted ascending, which is required for binary search to give correct results. The algorithm narrows the range from the full array down to a single index in just two comparisons instead of checking every element.
Example 3: Binary Search (Recursive)
public class Main {
static int binarySearch(int[] arr, int target, int low, int high) {
if (low > high) {
return -1;
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearch(arr, target, mid + 1, high);
} else {
return binarySearch(arr, target, low, mid - 1);
}
}
public static void main(String[] args) {
int[] sortedNumbers = {2, 4, 6, 8, 10, 12, 14, 16};
int target = 10;
int index = binarySearch(sortedNumbers, target, 0, sortedNumbers.length - 1);
if (index != -1) {
System.out.println(target + " found at index " + index);
} else {
System.out.println(target + " not found in array");
}
}
}Output:
10 found at index 4The recursive version expresses the exact same idea as the iterative one, but instead of looping, each call narrows low and high and calls itself on the smaller range. The base case low > high stops the recursion when the range is empty. Every recursive call needs its own stack frame, so for extremely large datasets the iterative version is slightly more memory-efficient — but for typical array sizes, both are equally fast in practice.
Example 4: Using the Built-in Arrays.binarySearch
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] sortedNumbers = {5, 12, 23, 34, 67, 78, 90};
int index = Arrays.binarySearch(sortedNumbers, 78);
System.out.println("Index of 78: " + index);
int missingIndex = Arrays.binarySearch(sortedNumbers, 50);
System.out.println("Index of 50: " + missingIndex);
}
}Output:
Index of 78: 5
Index of 50: -5Java’s standard library already implements binary search for you via Arrays.binarySearch (and Collections.binarySearch for lists). When the value is found, it returns its index. When it isn’t found, it returns a negative number encoding the position where the value would need to be inserted to keep the array sorted, calculated as -(insertionPoint) - 1. Here, 50 would sit between index 3 (34) and index 4 (67), so the insertion point is 4, and the method returns -4 - 1 = -5. In real projects, prefer the built-in method over writing your own — it’s tested, optimized, and avoids the bugs described below. Writing binary search by hand, as shown above, is mainly valuable for learning and for technical interviews.
How It Works Step by Step: Binary Search Under the Hood
Let’s trace Example 2 (searching for 67 in {5, 12, 23, 34, 67, 78, 90}, indices 0–6) to see exactly what the JVM does on each iteration.
| Step | low | high | mid | array[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 34 | 34 < 67, so search the right half: low = 4 |
| 2 | 4 | 6 | 5 | 78 | 78 > 67, so search the left half: high = 4 |
| 3 | 4 | 4 | 4 | 67 | Match! Return index 4 |
Each iteration reads the middle element directly from memory (an O(1) array access), compares it to the target with a single CPU instruction, and then discards half of the remaining search space by moving low or high. Because the search space is cut in half every time, an array of size n needs at most log₂(n) steps — for 7 elements that’s about 3 steps, matching the trace above exactly.
Common Mistakes
Mistake 1: Off-by-One Errors That Cause an Infinite Loop
A very common bug is updating low or high to mid instead of mid + 1 or mid - 1. This looks harmless but can cause the loop to never terminate, because the range stops shrinking:
// BUGGY: forgets to move past mid, can loop forever
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
result = mid;
break;
} else if (arr[mid] < target) {
low = mid; // should be mid + 1
} else {
high = mid; // should be mid - 1
}
}If low and high become adjacent (say low = 3, high = 4), mid computes to 3 again and again, and low never advances — the loop spins forever. Always move the boundary strictly past mid: use low = mid + 1 and high = mid - 1, exactly as shown in Example 2.
Mistake 2: Running Binary Search on an Unsorted Array
Binary search silently gives wrong answers — it does not throw an exception — if the array isn’t sorted, because its logic assumes that everything to the left of mid is smaller and everything to the right is larger:
public class Main {
public static void main(String[] args) {
int[] unsorted = {45, 12, 78, 3, 90, 34};
int target = 34;
int low = 0;
int high = unsorted.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (unsorted[mid] == target) {
result = mid;
break;
} else if (unsorted[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println("Result: " + result);
}
}Output:
Result: -1Even though 34 is clearly present at index 5, binary search reports it as missing, because the array isn’t sorted and the algorithm’s halving logic makes an incorrect assumption along the way. Always sort the array first with Arrays.sort(array) (or confirm it’s already sorted) before using binary search — or just use linear search if you can’t guarantee order.
Mistake 3: Integer Overflow When Computing the Midpoint
Writing int mid = (low + high) / 2; is a classic bug for very large arrays: if low and high are both close to Integer.MAX_VALUE, their sum can overflow and wrap around to a negative number, producing an invalid array index. The safe form, used throughout this lesson, avoids adding the two large numbers together: int mid = low + (high - low) / 2;. This computes the same midpoint but never risks overflow, since high - low is always a much smaller number than high or low individually.
Best Practices
- Use linear search for small or unsorted collections, or when you only search once — sorting first just to binary search once isn’t worth the O(n log n) sorting cost.
- Use binary search whenever data is already sorted and you’ll search it repeatedly — the O(log n) payoff compounds with every lookup.
- Prefer
Arrays.binarySearchorCollections.binarySearchover hand-written versions in production code; they’re well-tested and handle edge cases correctly. - Always compute the midpoint as
low + (high - low) / 2to avoid integer overflow on large arrays. - Double-check that data is truly sorted (in the order your comparison expects) before relying on binary search.
- For custom objects, make sure they implement
Comparableor that you supply aComparator, since both sorting and binary search rely on consistent ordering.
Practice Exercises
- Exercise 1: Write a linear search method that returns the index of the last occurrence of a target value in an array (instead of the first).
- Exercise 2: Modify the iterative binary search to count and print how many comparisons it takes to find a target in an array of 1,000 sorted elements, and compare that to how many comparisons linear search would need in the worst case.
- Exercise 3: Write a method
boolean isSorted(int[] arr)that checks whether an array is sorted in ascending order, and use it to guard a binary search method so it prints an error message instead of searching an unsorted array.
Summary
- Linear search checks every element in order; it works on any collection, sorted or not, in O(n) time.
- Binary search repeatedly halves a sorted range to find a target in O(log n) time, but requires the data to already be sorted.
- Binary search can be implemented iteratively (with a
whileloop) or recursively (with a base case oflow > high). - Java’s
Arrays.binarySearchandCollections.binarySearchprovide tested, built-in implementations for arrays and lists. - Common bugs include off-by-one errors causing infinite loops, running binary search on unsorted data, and integer overflow in the midpoint calculation — always compute
midaslow + (high - low) / 2.
