Binary Search — Use binary search conceptually (and via Arrays.binarySearch) (intro) - Java

SECTION 1

Historical Context & Motivation

Imagine trying to find a specific word in a 1,500-page dictionary. Would you flip through every single page from start to finish? Of course not — you would open the book roughly in the middle, check if your word comes before or after that page, and repeat the process in the remaining half. This intuitive strategy is exactly what binary search formalizes. It is one of the oldest and most fundamental ideas in computer science, turning a potentially slow lookup into a remarkably fast one.

1946 • First Published Description

John Mauchly describes the binary search idea during the Moore School Lectures, one of the earliest formal discussions of computer algorithms.

1960 • First Bug-Free Implementation

Despite its simplicity, a correct binary search implementation eluded programmers for over a decade. Derrick Henry Lehmer and others struggled with off-by-one errors, highlighting how tricky the details can be.

1986 • Jon Bentley's Famous Challenge

In his book Programming Pearls, Jon Bentley reported that only about 10% of professional programmers could write a correct binary search on the first try.

2006 • Integer Overflow Bug Fixed in Java

A subtle integer overflow bug was discovered in Java's own Arrays.binarySearch method — a bug that had existed for nearly a decade, proving that binary search details matter.

The central question binary search answers is simple: how can we find a target value in a sorted collection as quickly as possible? A naïve approach — checking each element one by one — works, but it is painfully slow for large datasets. Binary search solves this problem by eliminating half of the remaining elements with every comparison.

SECTION 2

Core Principles & Definitions

Binary search relies on a few key ideas that must all be in place for the algorithm to work correctly. If any one of these conditions is missing, the search can produce incorrect results. Let's walk through each foundational principle.

Sorted Data Required

The array (or list) must be sorted in ascending or descending order before binary search is applied. Without sorted data, the halving logic breaks down completely.

Divide and Conquer

At each step, the algorithm compares the target to the middle element of the current search range. Depending on the comparison, it discards one half and repeats in the other.

Three Possible Outcomes

Each comparison yields one of three results: the target equals the middle (found!), the target is less (search left half), or the target is greater (search right half).

Logarithmic Efficiency

Because the search space is halved each time, binary search runs in O(log n) time — dramatically faster than a linear scan's O(n) for large arrays.

✦

KEY TAKEAWAY

Think of binary search like a guessing game where someone picks a number between 1 and 100, and after every guess they tell you "higher" or "lower." You would always guess the middle of the remaining range — that way, you can guarantee finding the number in at most 7 guesses. A linear search, by contrast, might take up to 100 guesses. That's the power of halving the search space each time.

SECTION 3

Visual Explanation — Searching Step by Step

The diagram below illustrates how binary search narrows in on a target value of 23 within a sorted array of eight integers. Notice how the highlighted search range shrinks by half at each step, and how the pointer to the middle element shifts accordingly.

Each colored bar shows the remaining search range after a comparison. In Step 1 (cyan), the entire array is in play. By Step 2 (violet), only the right half remains. In Step 3 (pink), a single element is checked and the target 23 is found at index 4.

As the diagram shows, three comparisons are enough to locate the target in an eight-element array. A linear search would have needed up to eight comparisons in the worst case — checking every element from left to right. The larger the array, the bigger the gap between the two approaches. For a million elements, linear search might take a million checks, whereas binary search would need at most about 20.

SECTION 4

Mathematical Framework — Why O(log n)?

Understanding why binary search is so fast comes down to one mathematical idea: when you halve a number repeatedly, it shrinks to 1 very quickly. The number of times you can halve n before reaching 1 is called the base-2 logarithm of n, written log₂(n).

WORST-CASE COMPARISONS

Maximum comparisons = ⌊log₂(n)⌋ + 1

Where n is the number of elements in the sorted array, and ⌊ ⌋ denotes the floor function (round down).

MIDDLE INDEX FORMULA

mid = low + (high − low) / 2

This is preferred over (low + high) / 2 because the latter can cause integer overflow when low and high are both very large.

Array Size (n)	Linear Search (worst case)	Binary Search (worst case)
8	8 comparisons	4 comparisons
1,000	1,000 comparisons	10 comparisons
1,000,000	1,000,000 comparisons	20 comparisons
1,000,000,000	1,000,000,000 comparisons	30 comparisons

Comparison count growth: linear vs. binary search

The table above makes the dramatic difference clear. For a billion-element array, binary search needs only about 30 comparisons in the worst case, while a linear scan could require a billion. This is the magic of logarithmic growth — every time the data doubles in size, binary search needs just one extra comparison.

SECTION 5

Using Arrays.binarySearch in Java

Java provides a built-in binary search method so you don't have to write the algorithm from scratch. The Arrays.binarySearch method lives in the java.util.Arrays class and works on sorted arrays of primitives (like int[]) as well as arrays of objects. The array must be sorted before you call this method — if it is not, the results are unpredictable.

The flowchart shows how Arrays.binarySearch returns a non-negative index when the element is found, or a specially encoded negative value when it is not. You can recover the insertion point — where the element would go to keep the array sorted — by computing -(result) - 1.

⚠

Common Pitfall

If you forget to sort the array before calling Arrays.binarySearch, Java will not throw an error — it will simply return an incorrect or unpredictable result. Always call Arrays.sort(arr) first if the array is not already sorted.

Here is a minimal but complete Java example that demonstrates both the sorting step and the search:

💡

Sample Code

import java.util.Arrays;

public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] data = {42, 8, 23, 2, 14, 5, 37, 58};
        Arrays.sort(data);  // MUST sort first!
        // data is now {2, 5, 8, 14, 23, 37, 42, 58}

        int idx = Arrays.binarySearch(data, 23);
        System.out.println("Found 23 at index: " + idx);  // 4

        int missing = Arrays.binarySearch(data, 10);
        System.out.println("Search for 10: " + missing);  // -4
    }
}

SECTION 6

Worked Example — Tracing Binary Search by Hand

Let's trace through binary search manually on a sorted array to find the value 37. The array is: {3, 7, 11, 19, 25, 37, 44, 50, 62, 78} (10 elements, indices 0 through 9).

Find 37 in a 10-Element Sorted Array

1
Step 1 — Initialize Pointers

Set low = 0 and high = 9. The entire array is our search range.

Search range: indices 0 – 9 (all 10 elements)
2
Step 2 — First Comparison

Compute mid = 0 + (9 − 0) / 2 = 4. The value at index 4 is 25. Since 37 > 25, we discard the left half (indices 0–4) and set low = 5.

New range: indices 5 – 9 (5 elements remain)
3
Step 3 — Second Comparison

Compute mid = 5 + (9 − 5) / 2 = 7. The value at index 7 is 50. Since 37 < 50, we discard the right half (indices 7–9) and set high = 6.

New range: indices 5 – 6 (2 elements remain)
4
Step 4 — Third Comparison

Compute mid = 5 + (6 − 5) / 2 = 5. The value at index 5 is 37. This matches our target!

Target 37 found at index 5 after only 3 comparisons.
5
Step 5 — Verify with Java API

Calling Arrays.binarySearch(arr, 37) on this sorted array returns 5, confirming our manual trace. The worst case for 10 elements would be ⌊log₂(10)⌋ + 1 = 4 comparisons, so finding it in 3 is better than worst case.

Arrays.binarySearch returns 5 ✓

SECTION 7

Binary Search vs. Linear Search — Strengths & Limitations

Binary search is impressively fast, but it is not always the right tool. Understanding when to use it — and when a simpler approach might be better — is an important skill. The following table compares the two primary search strategies you'll encounter.

Feature	Linear Search	Binary Search
Time Complexity	O(n) — checks every element in the worst case	O(log n) — halves the search space each step
Requires Sorted Data?	No — works on any array, sorted or unsorted	Yes — the array must be sorted beforehand
Best for Small Arrays?	Yes — overhead is minimal	The speed advantage may not be noticeable
Best for Large Arrays?	Too slow — could need millions of checks	Yes — excels with large datasets
Implementation Difficulty	Very simple — just a for loop	Moderate — off-by-one errors are common
Java Built-in	No standard method (use a loop)	`Arrays.binarySearch()`

Linear search vs. binary search comparison

⚖

WHEN TO CHOOSE WHICH

Use linear search when your data is unsorted or the array is very small (say, under 20 elements). Use binary search when the data is already sorted (or when you need to search the same array many times — sort it once, search it many times). If you'll be searching frequently, the one-time cost of sorting pays for itself quickly.

SECTION 8

Connection to Advanced Concepts

Binary search is not just a standalone algorithm — it is a foundational idea that appears in many advanced data structures and algorithms. Once you are comfortable with the basic version, you will start seeing the divide-and-conquer pattern everywhere in computer science.

Concept	Intro Level (This Lesson)	Advanced Extension
Data Structure	Sorted array	Binary Search Trees (BSTs), balanced trees (AVL, Red-Black)
Search Scope	Finding an exact value	Finding ranges, closest values, lower/upper bounds
Algorithm Pattern	Iterative binary search	Recursive binary search, merge sort, quick sort (all use divide & conquer)
Java API	`Arrays.binarySearch()`	`Collections.binarySearch()` for Lists, `TreeMap` / `TreeSet`

How binary search concepts extend into advanced topics

In future courses, you may encounter binary search trees, where the halving principle is built directly into the data structure itself, allowing O(log n) search, insertion, and deletion without needing to re-sort. You will also see binary search adapted for problems like "find the first element greater than x" or "find the minimum value that satisfies a condition" — powerful variations used in competitive programming and real-world software.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Why does binary search require the array to be sorted? What would go wrong if you tried to use binary search on an unsorted array like {15, 3, 8, 22, 1, 47}?

Show answer

Binary search relies on the assumption that all values to the left of the middle are smaller and all values to the right are larger. When the array is unsorted, this assumption breaks. For example, if mid lands on 22, binary search might conclude that 3 must be in the right half (since 3 < 22), but 3 is actually at index 1 in the left half. The algorithm would search the wrong portion and either return an incorrect index or report the element as missing when it is actually present.

Question 2: BASIC CALCULATION

Given the sorted array {4, 9, 16, 25, 36, 49, 64}, how many comparisons does binary search need in the worst case? Use the formula ⌊log₂(n)⌋ + 1.

Show answer

The array has n = 7 elements. Calculating: log₂(7) ≈ 2.807, and ⌊2.807⌋ = 2. So the worst-case number of comparisons is 2 + 1 = 3. This means no matter which element you search for (or even if the target is missing), binary search will need at most 3 comparisons to determine the result. You can verify this: halving 7 gives roughly 3, then roughly 1 — three halvings total.

Question 3: INTERMEDIATE

Trace binary search step by step to find the value 19 in the sorted array {2, 7, 11, 15, 19, 24, 30}. Show the values of low, high, and mid at each step. What does Arrays.binarySearch return?

Show answer

Step 1: low=0, high=6, mid=3 → arr[3]=15. Since 19 > 15, set low=4. Step 2: low=4, high=6, mid=5 → arr[5]=24. Since 19 < 24, set high=4. Step 3: low=4, high=4, mid=4 → arr[4]=19. Match found! Binary search took 3 comparisons. Arrays.binarySearch returns 4 (the index where 19 is located). This is a non-negative value, confirming the element was found.

Question 4: APPLIED

You have a sorted array {10, 20, 30, 40, 50} and you call Arrays.binarySearch(arr, 35). The value 35 is not in the array. What does the method return, and how can you use that return value to determine where 35 would be inserted to keep the array sorted?

Show answer

Since 35 is not in the array, its insertion point would be index 3 (between 30 at index 2 and 40 at index 3). The return value is calculated as −(insertion point) − 1 = −(3) − 1 = −4. To recover the insertion point from the return value, compute −(−4) − 1 = 4 − 1 = 3. So you would insert 35 at index 3, shifting 40 and 50 to the right. This negative-return-value encoding is a clever design that lets a single int communicate both 'not found' and 'where it would go.'

Question 5: CRITICAL THINKING

A student writes the following binary search code but has a bug. Identify the problem and explain what could go wrong:

int low = 0, high = arr.length;  // bug is here
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
}

Show answer

The bug is that high is initialized to arr.length instead of arr.length − 1. Since array indices go from 0 to length − 1, when mid evaluates to arr.length (which can happen on the first iteration if the array has an odd length), accessing arr[mid] will throw an ArrayIndexOutOfBoundsException. The correct initialization is high = arr.length − 1. This is exactly the type of off-by-one error that makes binary search tricky to implement correctly — and it's precisely why Jon Bentley found that most programmers couldn't write a correct version on their first try. Using Java's built-in Arrays.binarySearch avoids this risk entirely.

SUMMARY

Lesson Summary

Summary

Binary search is an efficient algorithm for finding a target value in a sorted array. It works by repeatedly comparing the target to the middle element and discarding half of the remaining elements, achieving a time complexity of O(log n) — far faster than linear search's O(n) for large datasets. The middle index formula mid = low + (high − low) / 2 avoids integer overflow.

In Java, the Arrays.binarySearch() method handles the implementation for you: it returns the element's index if found, or a negative value encoding the insertion point if not found. Always remember that the array must be sorted first (use Arrays.sort()). Binary search is the gateway concept to divide-and-conquer algorithms and tree-based data structures you will encounter in more advanced courses.