Searching

Linear search

Check each element until you find what you want.

static int indexOf(int[] values, int target) {
    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) {
            return i;
        }
    }
    return -1;                        // not found
}

Returning -1 for “not found” is the Java convention — String.indexOf and List.indexOf both do it. Whatever you choose, make it impossible to confuse with a valid answer.

Linear search works on any data in any order, and it checks up to every element. For a few thousand items that is instant. It is the right default until you have a reason to do better.

Binary search

If the data is sorted, you can do much better. Look at the middle. If it is too big, the answer is in the left half; if too small, the right half. Each comparison discards half of what remains.

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;
        } else if (values[mid] < target) {
            low = mid + 1;            // answer is to the right
        } else {
            high = mid - 1;           // answer is to the left
        }
    }
    return -1;
}

A sorted array of a million elements takes about 20 comparisons instead of a million.

Those four together are why binary search is famously fiddly. Write it once carefully and test it on: an empty array, one element, the first element, the last element, and a value that is absent.

Use the library

For a plain lookup, Java already has it:

int[] values = {10, 20, 30, 40, 50};
int index = Arrays.binarySearch(values, 30);        // 2

List<String> names = List.of("alice", "bob", "carol");
int i = Collections.binarySearch(names, "bob");     // 1

Both require sorted input. When the value is absent they return a negative number encoding where it would go, which is occasionally useful and often surprising — so check for < 0 rather than == -1.

Finding a boundary

The more valuable use of binary search is not finding an exact value but finding where a condition changes. Suppose a list is sorted and you want the first element at or above a threshold:

// first index where values[index] >= target, or values.length if none
static int lowerBound(int[] values, int target) {
    int low = 0;
    int high = values.length;         // note: length, not length - 1

    while (low < high) {              // note: <, not <=
        int mid = low + (high - low) / 2;

        if (values[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;               // note: mid, not mid - 1
        }
    }
    return low;
}

The three differences from the exact-match version are deliberate and interlocking. This variant never “finds” anything — it narrows until low and high meet at the boundary. Changing one of the three without the others breaks it.

TreeSet gives you the same thing with no code:

TreeSet<Integer> set = new TreeSet<>(List.of(10, 20, 30));
System.out.println(set.ceiling(15));   // 20 — smallest >= 15
System.out.println(set.floor(15));     // 10 — largest <= 15

Hash-based lookup

When you only need “is this present” and order does not matter, a hash set beats both:

Set<Integer> seen = new HashSet<>(List.of(10, 20, 30));
System.out.println(seen.contains(20));   // true, effectively instant

Choosing a search

Next

Related