Wyszukiwanie liniowe i binarne w Javie z przykładami

Wyszukiwanie liniowe przechodzi tablicę od początku do końca i porównuje każdy element z szukaną wartością. Przy pierwszym trafieniu zwraca indeks. Jeśli dojdzie do końca i nic nie znajdzie, zwraca -1. -1 nigdy nie jest poprawnym indeksem, dlatego dobrze nadaje się jako znak „nie znaleziono”.

Wyszukiwanie liniowe działa z każdą tablicą, posortowaną czy nie, i z każdym typem. Napisy (String) porównujesz przy tym przez equals, a nie przez ==.

1public class Main {2    public static int indexOf(int[] numbers, int target) {3        for (int i = 0; i < numbers.length; i++) {4            if (numbers[i] == target) {5                return i;6            }7        }8        return -1;9    }10
11    public static void main(String[] args) {12        int[] numbers = {42, 7, 19, 3, 7};13        System.out.println(indexOf(numbers, 7));14        System.out.println(indexOf(numbers, 3));15        System.out.println(indexOf(numbers, 99));16    }17}

Warianty łatwo zbudować: dla ostatniego trafienia pętla biegnie od tyłu, przy liczeniu przechodzi całą tablicę, a dla minimum lub maksimum zapamiętujesz indeks najlepszego dotąd elementu.

Jeśli tablica jest posortowana rosnąco, da się to zrobić dużo szybciej. Wyszukiwanie binarne patrzy na środek przedziału:

• Jeśli wartość w środku jest równa szukanej, koniec.
• Jeśli jest mniejsza, cel może leżeć tylko na prawo od niej: lo = mid + 1.
• Jeśli jest większa, cel może leżeć tylko na lewo od niej: hi = mid - 1.

lo i hi to granice przedziału, który jeszcze wchodzi w grę, obie włącznie. Pętla działa, dopóki przedział nie jest pusty, czyli while (lo <= hi). W każdym kroku przedział zmniejsza się o połowę.

1public class Main {2    public static int binarySearch(int[] sorted, int target) {3        int lo = 0;4        int hi = sorted.length - 1;5        while (lo <= hi) {6            int mid = lo + (hi - lo) / 2;7            System.out.println("lo=" + lo + " mid=" + mid + " hi=" + hi);8            if (sorted[mid] == target) {9                return mid;10            } else if (sorted[mid] < target) {11                lo = mid + 1;12            } else {13                hi = mid - 1;14            }15        }16        return -1;17    }18
19    public static void main(String[] args) {20        int[] sorted = {3, 7, 19, 25, 42, 56, 80};21        System.out.println("Found at " + binarySearch(sorted, 56));22    }23}

Ten sam pomysł działa też rekurencyjnie: metoda dostaje lo i hi jako parametry i wywołuje samą siebie dla odpowiedniej połowy. Warunkiem zakończenia jest lo > hi (nie znaleziono) albo trafienie w środku.

Szybkości algorytmu nie mierzy się w sekundach, tylko tym, jak liczba kroków rośnie wraz z rozmiarem n danych wejściowych. Zapisuje się to w notacji dużego O:

• Wyszukiwanie liniowe potrzebuje w najgorszym przypadku n porównań. Dwa razy więcej danych, dwa razy więcej kroków: O(n).
• Wyszukiwanie binarne w każdym kroku dzieli przedział na pół. Po około log₂ n krokach zostaje tylko jeden element: O(log n).

Przy milionie elementów to milion porównań wobec około 20. W zamian tablica musi być posortowana, a samo sortowanie też kosztuje czas (więcej o tym w artykułach o prostych algorytmach sortowania i szybkich algorytmach sortowania). Jeśli szukasz tylko raz, często wystarczy wyszukiwanie liniowe. Jeśli często szukasz w tej samej tablicy, sortowanie się opłaca.

1public class Main {2    public static int linearSteps(int[] sorted, int target) {3        int steps = 0;4        for (int value : sorted) {5            steps++;6            if (value == target) {7                break;8            }9        }10        return steps;11    }12
13    public static int binarySteps(int[] sorted, int target) {14        int steps = 0;15        int lo = 0;16        int hi = sorted.length - 1;17        while (lo <= hi) {18            steps++;19            int mid = lo + (hi - lo) / 2;20            if (sorted[mid] == target) {21                break;22            } else if (sorted[mid] < target) {23                lo = mid + 1;24            } else {25                hi = mid - 1;26            }27        }28        return steps;29    }30
31    public static void main(String[] args) {32        for (int n = 10; n <= 1_000_000; n *= 10) {33            int[] sorted = new int[n];34            for (int i = 0; i < n; i++) {35                sorted[i] = 2 * i;36            }37            int target = sorted[n - 1];38            System.out.println("n=" + n39                    + "  linear: " + linearSteps(sorted, target)40                    + "  binary: " + binarySteps(sorted, target));41        }42    }43}

W prawdziwych programach rzadko piszesz wyszukiwanie sam. Arrays.binarySearch szuka binarnie w posortowanej tablicy, List.indexOf i List.contains szukają liniowo w liście.

Jeśli wartości brakuje, Arrays.binarySearch nie zwraca -1, tylko -(punkt wstawienia) - 1. Punkt wstawienia to miejsce, w którym wartość musiałaby stać, żeby tablica pozostała posortowana. W przykładzie 10 należy na indeks 2, więc wynikiem jest -3.

1import java.util.Arrays;2import java.util.List;3
4public class Main {5    public static void main(String[] args) {6        int[] numbers = {42, 7, 19, 3};7        Arrays.sort(numbers);8        System.out.println(Arrays.toString(numbers));9        System.out.println(Arrays.binarySearch(numbers, 19));10        System.out.println(Arrays.binarySearch(numbers, 10));11
12        List<String> names = List.of("Ali", "Mia", "Tom");13        System.out.println(names.indexOf("Mia"));14        System.out.println(names.contains("Eva"));15    }16}