Brewlearn Get the app
🧠 Data Structures & Algorithms · Advanced

Linear vs binary search in Java

Binary search needs sorted data; off-by-one and overflow in (lo+hi)/2.

🧩 The mysteryI'm thinking of a number from 1 to 100. You'll always find it in 7 guesses or fewer, if I tell you "higher" or "lower". That's binary search.

Two ways to find something

Linear search checks items one by one: O(n), and it works on any data. Binary search looks at the middle of a sorted range and throws away the half that can't contain the key: O(log n). A million sorted items need only about 20 comparisons.

The algorithm

Keep an inclusive range lo..hi. Look at the middle. Found it? Done. Too small? The key must be right of mid. Too big? Left of it. The loop runs **while lo <= hi**, i.e., while at least one candidate remains.

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

Trace the rounds

How many rounds does it take to find 23?

int[] a = {2, 5, 8, 12, 16, 23, 38};
int lo = 0, hi = a.length - 1, rounds = 0;
while (lo <= hi) {
    rounds++;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == 23) break;
    if (a[mid] < 23) lo = mid + 1;
    else hi = mid - 1;
}
System.out.println(rounds);
  1. 2
  2. 3
  3. 6
Show the answer

Round 1: lo 0, hi 6, mid 3, a[3] = 12 is too small, so lo = 4. Round 2: mid = 4 + (6 - 4) / 2 = 5, and a[5] = 23. Found in 2 rounds; linear search would need 6.

⚠️ The trap

The overflow bug

(lo + hi) / 2 looks right and passes every test. But on arrays with more than about a billion elements, lo + hi can exceed Integer.MAX_VALUE and wrap to a negative number, giving a negative index. Use lo + (hi - lo) / 2 or (lo + hi) >>> 1.

int mid = (lo + hi) / 2;       // can overflow
int mid = lo + (hi - lo) / 2;  // safe
int mid = (lo + hi) >>> 1;     // safe too
🤔 Think first

The off-by-one

With inclusive bounds (hi = a.length - 1), someone writes while (lo < hi). What goes wrong?

Think about it, then reveal the answer

When the range shrinks to lo == hi, one candidate is left but never checked. Searching for the last element, for example, returns -1. With inclusive bounds the condition must be lo <= hi.

🔮 Predict it

The library version

Arrays.binarySearch returns -(insertionPoint) - 1 when the key is missing. What does this print?

int[] a = {10, 20, 30};
System.out.println(Arrays.binarySearch(a, 20));
System.out.println(Arrays.binarySearch(a, 5));
System.out.println(Arrays.binarySearch(a, 35));
  1. 1 -1 -4
  2. 1 -1 -1
  3. 1 0 3
Show the answer

20 is at index 1. 5 would be inserted at index 0, giving -(0) - 1 = -1. 35 would go at index 3: -(3) - 1 = -4. The extra -1 makes "insert at 0" distinguishable from "found at 0".

When linear wins

Binary search requires sorted data. On unsorted data it may throw away the half that holds the key, even if the key is there. And for a single search of unsorted data, just scan: sorting costs O(n log n), more than one O(n) pass. Sorting pays off only when you'll search many times.

💼 In the real world

In practice

Use Arrays.binarySearch and Collections.binarySearch rather than writing your own. The same halving idea powers database indexes, git bisect for finding the commit that broke a build, and "find the first bad version" interview questions.

Key takeaways

  1. Binary search requires sorted input
  2. Safe midpoint: lo + (hi - lo) / 2 or (lo + hi) >>> 1
  3. Arrays.binarySearch returns -(insertionPoint) - 1 if missing
  4. A million sorted items need only about 20 comparisons

💡 Finding a word in a dictionary: open the middle, then throw away the half that can't contain it.

🤯 Did you know?

In 2006 Joshua Bloch revealed that the (low + high) / 2 overflow bug had been hiding in the JDK's own Arrays.binarySearch, which he wrote, for nine years or so.

Practice questions

What does this print?

int[] a = {10, 20, 30, 40};
System.out.println(Arrays.binarySearch(a, 30));
System.out.println(Arrays.binarySearch(a, 25));
  1. 2 -3
  2. 2 -1
  3. 2 -2
  4. 3 -3
Check your answer

2 -3. 30 is at index 2. 25 is missing; it would be inserted at index 2, so the result is -(2) - 1 = -3. The -1 shift makes 'insert at 0' distinguishable from 'found at 0'.

What does this print?

int[] a = {1, 3, 5, 7};
int lo = 0, hi = a.length - 1, key = 7;
int found = -1;
while (lo < hi) {
    int mid = (lo + hi) >>> 1;
    if (a[mid] == key) { found = mid; break; }
    if (a[mid] < key) lo = mid + 1;
    else hi = mid - 1;
}
System.out.println(found);
  1. -1
  2. 3
  3. 2
  4. Loops forever
Check your answer

-1. The range shrinks to lo = hi = 3, but lo < hi is then false, so index 3 is never checked. With inclusive bounds the condition must be lo <= hi.

Next: three simple sorts, and why the "slow" one is secretly inside Java's fastest sorts.