Linear search checks candidates in sequence until it finds a match or exhausts the input. Binary search repeatedly halves a sorted search interval. Both can find a value, but they have different preconditions and growth patterns. A beginner-friendly search contract states what the method returns for a match, what absence means, and how duplicates are handled. This lesson uses array indices and returns minus one for absence, while also explaining the different absence encoding used by Arrays.binarySearch.
Linear search works without sorting
A linear scan compares each element with the target. Returning immediately finds the first matching index under the scan order. In the worst case, it checks every element, taking O(n) time and constant auxiliary space for an array. It works on unsorted data and is often appropriate for small inputs or a single search. Sorting first merely to search once may cost more than scanning.
Binary search requires a compatible order
Binary search assumes the input is sorted by the same ordering used for comparisons. It inspects a middle element and discards the half that cannot contain the target. On a sorted array this takes O(log n) comparisons. Applying it to unsorted input can return an incorrect absence result without an exception, so the precondition must be explicit. A collection with slow indexed access may not offer the same practical benefit as an array.
Define interval boundaries consistently
The sample uses inclusive low and high bounds. The loop continues while low is less than or equal to high, ensuring the last candidate is checked. If the middle value is too small, low becomes middle plus one; if too large, high becomes middle minus one. Each update removes the inspected candidate and reduces the interval. Mixing inclusive and exclusive conventions is a common source of skipped values and infinite loops.
Calculate the middle without unnecessary overflow
Use low + (high - low) / 2 when the indices are nonnegative and ordered. Computing (low + high) / 2 can overflow for very large positive bounds before division occurs. The safe expression bases the offset on interval length. Overflow may not appear in a tiny tutorial array, but learning the correct formula avoids a hidden defect when the same algorithm is reused with large data.
Specify the duplicate policy
A basic binary search can return any matching duplicate; it does not automatically promise the first or last match. Finding the first occurrence requires continuing toward the left after a match and retaining the best index found. Linear search from the start naturally returns the first match. Select the contract that callers actually need and test repeated values. Do not interpret one observed binary-search duplicate index as a guarantee for every implementation.
Use the library absence contract correctly
Arrays.binarySearch returns a nonnegative index for a found value. For absence, it returns a negative encoding of the insertion point: minus insertion point minus one. Recover the insertion point with -result - 1. This is richer than simply returning minus one because it describes where the value could be inserted to preserve order. Always test result >= 0 for presence rather than checking only result != -1.
Practice tasks and checks
Test both custom methods with an empty array, one element, the first value, the last value, and an absent target between two sorted values. For the linear method, include duplicates and assert the first index. For binary search, avoid asserting a specific duplicate index unless you extend its contract. Add a comparison counter and compare linear and binary searches on a sorted array with many elements. Then try binary search on deliberately unsorted input only as an invalid-precondition experiment and explain why any apparent success is not a guarantee. Finally, use the decoded library insertion point to build a new sorted array containing an absent value. Keep the returned negative encoding separate from actual indices.
Java Summary
- Binary search requires sorted data under the same comparison rule.
- Keep interval bounds and updates consistent.
- Decode negative library results before using an insertion point.
- Continue with sorting algorithms when these examples are clear.
Java Examples
Each example shows the code, the output it produces and what each part does.
Find the first match in unsorted data
Save this program as LinearSearchDemo.java. Compile it with javac LinearSearchDemo.java and run it with java LinearSearchDemo.
Expected output:
The scan begins at index zero, where eight already matches, so it returns zero without examining later values. Searching for seven reaches every element and returns minus one. The duplicate eight at index two does not change the first-match contract. An empty array simply skips the loop and returns absence, so the same method handles that boundary without a separate indexing operation.
public class LinearSearchDemo {
static int find(int[] values, int target) {
for (int i = 0; i < values.length; i++) {
if (values[i] == target) return i;
}
return -1;
}
public static void main(String[] args) {
int[] values = {8, 3, 8, 5};
System.out.println(find(values, 8));
System.out.println(find(values, 7));
}
}0
-1Halve a sorted interval
Save this program as BinarySearchDemo.java. Compile it with javac BinarySearchDemo.java and run it with java BinarySearchDemo.
Expected output:
The initial middle is index two, containing nine. For target fourteen, the search moves to the right half, whose middle is index three, and returns that index. For seven, the bounds narrow around values that straddle the target until no candidates remain. The sorted array makes each discard valid. The empty-array high bound becomes minus one, so the loop does not attempt an invalid access.
public class BinarySearchDemo {
static int find(int[] values, int target) {
int low = 0, high = values.length - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (values[middle] == target) return middle;
if (values[middle] < target) low = middle + 1;
else high = middle - 1;
}
return -1;
}
public static void main(String[] args) {
int[] values = {2, 5, 9, 14, 20};
System.out.println(find(values, 14));
System.out.println(find(values, 7));
}
}3
-1Decode a library insertion point
Save this program as LibrarySearch.java. Compile it with javac LibrarySearch.java and run it with java LibrarySearch.
Expected output:
Nine is found at index two. Seven is absent and belongs before nine, also at insertion point two. The library encodes that point as minus three, and the final calculation recovers two. Inserting seven at that position would preserve sorted order. Do not use the negative result directly as an array index, and do not assume every absent search returns minus one.
import java.util.Arrays;
public class LibrarySearch {
public static void main(String[] args) {
int[] values = {2, 5, 9, 14};
int found = Arrays.binarySearch(values, 9);
int absent = Arrays.binarySearch(values, 7);
System.out.println(found);
System.out.println(absent);
System.out.println(-absent - 1);
}
}2
-3
2Java FAQ
Should I sort before every binary search?
No. Sort when the data can remain ordered across enough searches to justify the cost, or maintain an ordered structure. Repeatedly sorting unchanged data wastes work; a single unsorted search often favors a linear scan.
Does binary search return the first duplicate?
Not in its basic or general library contract. If the first occurrence matters, use an explicitly designed lower-bound search or a suitable linear scan and test that contract.
How many steps does binary search take?
At most about log₂ n comparisons, because each step halves the remaining range. A sorted array of a million elements needs about 20 steps, and a billion needs about 30. A linear search of the same million elements may need a million comparisons.
Can I binary search a List in Java?
Yes, with Collections.binarySearch(list, key) on a list sorted in the same order. It returns the index when found, such as 2 for 8 in [2, 5, 8, 13], and a negative insertion point otherwise. It's fast for ArrayList; on a LinkedList, reaching the middle positions is slow.
When is linear search the better choice?
When the data is unsorted and you only search once or twice, when the collection is small, or when you need the first match by position. Sorting just to binary search once costs more than a single linear scan.
Java Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
What is the crucial precondition for binary search here?
Why does the loop use low <= high?
Java Quiz
2 questions to check what you learned.
How is a missing library result converted to an insertion point?
- -result - 1
- result + 1
- result squared
Which index does the linear example return for the first eight?
- 0
- 2
- -1