jario_
Back to overview

Algorithms and Data Structures · Chapter 1

Searching

Is a value in the array, and if so, where? Almost every program asks this question, whether it looks up a customer number or finds a name in a list. In this chapter, you get to know the two classic methods: linear and binary search. And for the first time, you see how to measure how fast an algorithm is.

Linear search

Linear search walks through the array from front to back and compares every element with the value it looks for. On the first match, it returns the index. If it reaches the end without finding anything, it returns -1. -1 is never a valid index, so it works well as a sign for "not found".

Linear search works with any array, sorted or not, and with any type. For strings, compare with equals, not with ==.

public class Main {    public static int indexOf(int[] numbers, int target) {        for (int i = 0; i < numbers.length; i++) {            if (numbers[i] == target) {                return i;            }        }        return -1;    }
    public static void main(String[] args) {        int[] numbers = {42, 7, 19, 3, 7};        System.out.println(indexOf(numbers, 7));        System.out.println(indexOf(numbers, 3));        System.out.println(indexOf(numbers, 99));    }}

Variations are quick to build: for the last match, the loop runs backwards, for counting, it runs all the way through, and for the minimum or maximum, you remember the index of the best element so far.

Binary search

If the array is sorted in ascending order, it gets much faster. Binary search looks at the middle of the range:

  • If the value there equals the one it looks for, it is done.
  • If it is smaller, the target can only be to the right: lo = mid + 1.
  • If it is larger, the target can only be to the left: hi = mid - 1.

lo and hi are the bounds of the range that is still possible, both inclusive. The loop runs as long as the range is not empty, so with while (lo <= hi). With every step, the range is cut in half.

public class Main {    public static int binarySearch(int[] sorted, int target) {        int lo = 0;        int hi = sorted.length - 1;        while (lo <= hi) {            int mid = lo + (hi - lo) / 2;            System.out.println("lo=" + lo + " mid=" + mid + " hi=" + hi);            if (sorted[mid] == target) {                return mid;            } else if (sorted[mid] < target) {                lo = mid + 1;            } else {                hi = mid - 1;            }        }        return -1;    }
    public static void main(String[] args) {        int[] sorted = {3, 7, 19, 25, 42, 56, 80};        System.out.println("Found at " + binarySearch(sorted, 56));    }}

The same idea also works recursively: the method gets lo and hi as parameters and calls itself with the matching half. The base case is lo > hi (not found) or a match in the middle.

Running time: O(n) and O(log n)

How fast an algorithm is isn't measured in seconds, but by how the number of steps grows with the size n of the input. This is written in big O notation:

  • Linear search needs n comparisons in the worst case. Twice as much data, twice as many steps: O(n).
  • Binary search halves the range with every step. After about log₂ n steps, only one element is left: O(log n).

With a million elements, that is a million comparisons against about 20. In return, the array has to be sorted, and sorting takes time itself (more on that in the next chapters). If you search only once, linear search is often enough. If you search the same array often, sorting pays off.

public class Main {    public static int linearSteps(int[] sorted, int target) {        int steps = 0;        for (int value : sorted) {            steps++;            if (value == target) {                break;            }        }        return steps;    }
    public static int binarySteps(int[] sorted, int target) {        int steps = 0;        int lo = 0;        int hi = sorted.length - 1;        while (lo <= hi) {            steps++;            int mid = lo + (hi - lo) / 2;            if (sorted[mid] == target) {                break;            } else if (sorted[mid] < target) {                lo = mid + 1;            } else {                hi = mid - 1;            }        }        return steps;    }
    public static void main(String[] args) {        for (int n = 10; n <= 1_000_000; n *= 10) {            int[] sorted = new int[n];            for (int i = 0; i < n; i++) {                sorted[i] = 2 * i;            }            int target = sorted[n - 1];            System.out.println("n=" + n                    + "  linear: " + linearSteps(sorted, target)                    + "  binary: " + binarySteps(sorted, target));        }    }}

Searching with the standard library

In real programs, you rarely write the search yourself. Arrays.binarySearch searches a sorted array with binary search, List.indexOf and List.contains search a list linearly.

If the value is missing, Arrays.binarySearch doesn't return -1, but -(insertion point) - 1. The insertion point is the position where the value would have to be so that the array stays sorted. In the example, 10 belongs at index 2, so the result is -3.

import java.util.Arrays;import java.util.List;
public class Main {    public static void main(String[] args) {        int[] numbers = {42, 7, 19, 3};        Arrays.sort(numbers);        System.out.println(Arrays.toString(numbers));        System.out.println(Arrays.binarySearch(numbers, 19));        System.out.println(Arrays.binarySearch(numbers, 10));
        List<String> names = List.of("Ali", "Mia", "Tom");        System.out.println(names.indexOf("Mia"));        System.out.println(names.contains("Eva"));    }}

Common mistakes

  • Binary search on unsorted data

    Binary search relies on everything left of mid being smaller and everything right of it being larger. If the array isn't sorted, it doesn't throw an error, it simply returns wrong results, for example -1 for a value that is there. Sort first or use linear search.

  • Off-by-one in the condition and bounds

    If lo and hi are both inclusive, the loop must be while (lo <= hi). With lo < hi, the last remaining element is never checked, and the search misses values at the edges. Just as important: lo = mid + 1 and hi = mid - 1. With lo = mid, the loop can run forever, because the range no longer shrinks.

  • Overflow in (lo + hi) / 2

    With very large arrays, lo + hi can get larger than the largest int value and turn negative. Then mid is an invalid index. This is safe:

    int mid = lo + (hi - lo) / 2;

    hi - lo is never larger than the length of the array, so nothing can overflow here. For arrays in exercises, both are correct, but in an exam the safe form makes a good impression.