2.4 Binary Search | Code Scholars Tutoring

How it works

Binary search halves the search range each step and therefore costs log n, but it requires sorted input as a precondition.

Verify the sorted precondition, then compute the midpoint in a way that cannot overflow.

Common error

Running binary search on unsorted data, which returns a wrong answer confidently rather than failing.

Worked example

Java snippets run inside a main method. Add import java.util.*; when collection types are used.

Java

int[] a = {2, 5, 8, 11, 14};
int low = 0, high = a.length - 1, found = -1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (a[mid] == 11) { found = mid; break; }
    if (a[mid] < 11) low = mid + 1;
    else high = mid - 1;
}
System.out.println(found);

Output

The search interval is inclusive at both ends. Sorted order justifies discarding one half after each comparison; moving past mid is essential for progress.

Exercises

2.4.1 · Explain

On [2, 5, 8, 11, 14], what midpoint indices are checked when searching for 2?

Show solution

The search checks index 2, then index 0, finding 2. The first comparison moves high to 1.

2.4.2 · Write code

Implement iterative binary search for a sorted int array. Demonstrate a present target and an absent target.

Show solution

Keep an inclusive search interval and move past the tested midpoint. Return -1 for absence.

One valid solution

class Search {
    int find(int[] a, int target) {
        int low = 0, high = a.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == target) return mid;
            if (a[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }
}
Search s = new Search();
System.out.println(s.find(new int[]{2,5,8,11}, 8));
System.out.println(s.find(new int[]{2,5,8,11}, 7));

Expected output

2
-1

Open Java compiler