4.3.4.1–4.3.4.3 - Linear, binary and binary-tree search (Java)

Linear search

Linear search checks items in sequence until it finds the target or reaches the end, so it works even when the data is unordered.

This Java method returns the first matching index, or −1 if absent. Methods belong inside a class. Array indices start at zero.

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

For [18,7,23,7] and target7 it checks index0 then1 and returns1. It never examines the later7. To return the last occurrence instead, keep a candidate initially −1, overwrite it whenever a match is seen and finish scanning before returning. An empty array performs no comparisons and returns −1.

The worst case, including an absent target, compares all $n$ items. Doubling n roughly doubles this work, giving $O(n)$ worst-case time. A first-item match is constant work, $O(1)$; a best case does not change the worst-case classification.

Binary search on ordered data

Binary search discards half the remaining search interval by comparing the target with its middle item, which requires sorted data.

For an ascending array, a target smaller than the middle item can only be to its left; a larger target can only be to its right. Both limits are inclusive in this version. The middle item's index is excluded after an unsuccessful comparison, so the interval shrinks even when only one item remains.

static int binarySearch(int[] values, int target) {
    int low = 0, high = values.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (values[mid] == target) return mid;
        if (target < values[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}