Binary search

Look at the middle. If it is the target, done. If the target is smaller, discard the upper half; otherwise discard the lower. Repeat.

That is O(log n) — a million elements in about twenty comparisons.

Use the library

int i = Arrays.binarySearch(sorted, target);
List<String> list = ...;
int j = Collections.binarySearch(list, target);

The array must already be sorted. On unsorted data the result is meaningless rather than merely wrong — it does not throw, it returns nonsense.

The return value

Not just an index:

• Zero or positive: the index where the value was found.
• Negative: not found, and the value encodes where it would go, as -(insertionPoint) - 1.

That encoding exists so “not found” and “found at index 0” are distinguishable. To get the insertion point:

int i = Arrays.binarySearch(a, target);
if (i < 0) {
    int insertAt = -i - 1;
}

Which is exactly how you insert into a sorted list while keeping it sorted.

Writing it yourself

int lo = 0, hi = a.length - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
return -1;

Two details that are the whole difficulty.

The midpoint. (lo + hi) / 2 overflows when lo + hi exceeds Integer.MAX_VALUE, giving a negative index. lo + (hi - lo) / 2 cannot. This bug existed in the JDK’s own implementation for nine years, so it is not a beginner’s mistake.

The bounds. hi starts at length - 1 and the condition is <=. Change either and the loop either misses the last element or never terminates. Off-by-one here is the classic exercise for a reason.

When it is worth it

Sorting costs O(n log n). One search of unsorted data costs O(n). So sorting in order to binary search once is slower than just scanning. It pays when you search the same data repeatedly — and if lookups are the point, a HashMap at O(1) usually beats both.