Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / Java

Wyszukiwanie liniowe w Javie

Wyszukiwanie liniowe w Javie: Wyszukiwanie liniowe w Javie sprawdza elementy kolejno aż do dopasowania; List.indexOf używa equals, zwraca najniższy pasujący indeks albo -1.

Wersja: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime

Składnia

linear search

Wyszukiwanie liniowe w Javie sprawdza elementy kolejno aż do dopasowania; List.indexOf używa equals, zwraca najniższy pasujący indeks albo -1.

Stosuj je dla małej lub nieposortowanej sekwencji, jednorazowego zapytania albo predykatu, dla którego nie istnieje użyteczny indeks.

Pętla get(i) na LinkedList zmienia liniowy skan w O(n²); użyj Iterator lub enhanced for, a dla własnego porównania Objects.equals obsłuży null.

Pusta sekwencja i brak wyniku dają -1, duplikaty kończą się na pierwszym trafieniu, a tablice typów prostych porównuje się wartościowo operatorem ==.

List.indexOf znajduje pierwsze blue jako first-blue=1 i brak jako missing=-1; własny skan kończy się na green@2,checks=3 po trzech porównaniach.

Przykłady

import java.util.List;

public class Main {
    static int checks;

    static int findLength(List<String> values, int length) {
        for (int i = 0; i < values.size(); i++) {
            checks++;
            if (values.get(i).length() == length) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        var values = List.of("red", "blue", "green", "blue");
        System.out.println("first-blue=" + values.indexOf("blue"));
        System.out.println("missing=" + values.indexOf("black"));
        int index = findLength(values, 5);
        System.out.println(values.get(index) + "@" + index + ",checks=" + checks);
    }
}

Wynik

first-blue=1
missing=-1
green@2,checks=3

List.indexOf znajduje pierwsze blue jako first-blue=1 i brak jako missing=-1; własny skan kończy się na green@2,checks=3 po trzech porównaniach.

Źródła