College Board Unit 4
How it works
Linear search checks elements one at a time and works on any data, taking up to n comparisons. Binary search requires sorted data and repeatedly halves the range: compute the midpoint, compare, then discard the half that cannot contain the target. The bounds must exclude the midpoint on each update, using low = mid + 1 or high = mid - 1, and the loop continues while low is less than or equal to high.
Check that data is sorted before choosing binary search, and compute the midpoint safely.
Common error
Applying binary search to unsorted data, which returns a confidently wrong answer rather than failing.
Worked example
Java
int[] sorted = {2,5,8,11,14};
int low = 0;
int high = sorted.length - 1;
int mid = (low + high) / 2;
System.out.println(mid + ":" + sorted[mid]);Output
2:8The midpoint divides the five-element search interval. Compare its value with the target before updating a bound.
Exercises
8.3.1 · Trace
Determine the exact output. Explain the Java rule or state changes that produce it.
Java
int[] sorted = {2,5,8,11,14};
int low = 0;
int high = 4;
int mid = (low + high) / 2;
if (sorted[mid] < 11) low = mid + 1;
System.out.println(low + ":" + high);Show solution
Output
3:4Because the midpoint value is below the target, discard it and every smaller index.
8.3.2 · Write code
Write public static int binarySearch(int[] values, int target) for an ascending sorted array. Return a matching index or -1. Use an iterative loop.
Show solution
One valid solution is shown below. Other implementations satisfying the contract are also valid.
Java
public static int binarySearch(int[] values, int target) {
int low = 0;
int high = values.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (values[mid] == target) return mid;
if (values[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}Check your code
Java
System.out.println(binarySearch(new int[]{2,5,8,11,14},14));
System.out.println(binarySearch(new int[]{2,5,8},4));
System.out.println(binarySearch(new int[]{},4));Expected output
4
-1
-1