Wyszukiwanie liniowe
Algorytm wyszukiwania liniowego
Algorytm wyszukiwania liniowego przechodzi przez każdy element tablicy sekwencyjnie. Jeśli konkretny element nie pasuje do klucza wyszukiwania, algorytm przechodzi do następnego elementu aż do osiągnięcia końca tablicy, co pozwala poinformować, że klucz wyszukiwania nie istnieje. Jeżeli klucz wyszukiwania znajduje się w tablicy, algorytm testuje każdy element aż do znalezienia
takiego, który pasuje. Gdy go zlokalizuje, zwraca jego indeks. Przyjrzyjmy się tablicy zawierającej następujące wartości:
i programowi, który poszukuje wartości 51. Wykorzystując algorytm liniowy, program najpierw sprawdza, czy 34 pasuje do klucza wyszukiwania. Nie pasuje, więc algorytm sprawdza 56. Program kontynuuje działanie, sprawdzając po kolei: 2, potem 10 i 77. Gdy program sprawdzi 51, które pasuje do klucza wyszukiwania, zakończy działanie, zwracają indeks 5, czyli miejsce występowania 51 w tablicy. Jeśli po sprawdzeniu każdego elementu program stwierdzi, że klucz wyszukiwania do niczego nie pasuje, zwróci wartość znacznikową (np. -1).
Implementacja wyszukiwania liniowego
Klasa LinearSearchTest (rysunek 19.2) zawiera metodę statyczną linearSearch dokonującą wyszukiwania liniowego w tablicy wartości typu int i metodę main testującą algorytm.
1 // Rysunek 19.2. LinearSearchTest.java
2 // Sekwencyjne przeszukiwanie tablicy w celu znalezienia elementu
3 import java.security.SecureRandom;
4 import java.util.Arrays;
5 import java.util.Scanner;
6
7 public class LinearSearchTest {
8 // Wykonuje liniowe wyszukiwanie w danych
9 public static int linearSearch(int data[], int searchKey) {
10 // Przejdź przez tablicę sekwencyjnie
11 for (int index = 0; index < data.length; index++) {
12 if (data[index] == searchKey) {
13 return index; // Zwróć indeks
14 }
15 }
16
17 return -1; // Liczby nie znaleziono
18 }
19
20 public static void main(String[] args) {
21 Scanner input = new Scanner(System.in);
22 SecureRandom generator = new SecureRandom();
23
24 int[] data = new int[10]; // Utworzenie tablicy
25
26 for (int i = 0; i < data.length; i++) { // Wypełnienie tablicy
27 data[i] = 10 + generator.nextInt(90);
28 }
29
30 System.out.printf("%s%n%n", Arrays.toString(data)); // Wyświetlenie tablicy
31
32 // Pobranie danych od użytkownika
33 System.out.print("Wpisz liczbę całkowitą (-1, aby zakończyć): ");
34 int searchInt = input.nextInt();
35
36 // Pobieranie w pętli liczby całkowitej; -1 przerywa program
37 while (searchInt != -1) {
38 int position = linearSearch(data, searchInt); // Przeprowadzenie wyszukiwania
39
40 if (position == -1) { // Nie znaleziono
41 System.out.printf("%d nie znaleziono%n%n", searchInt);
42 }
43 else { // Znaleziono
44 System.out.printf("%d znaleziono na pozycji %d%n%n",
45 searchInt, position);
46 }
47
48 // Pobranie danych od użytkownika
49 System.out.print("Wpisz liczbę całkowitą (-1, aby zakończyć): ");
50 searchInt = input.nextInt();
51 }
52 }
53 }
Wpisz liczbę całkowitą (-1, aby zakończyć): 79
79 znaleziono na pozycji 4
Wpisz liczbę całkowitą (-1, aby zakończyć): 61
61 nie znaleziono
Wpisz liczbę całkowitą (-1, aby zakończyć): 51
51 znaleziono na pozycji 7
Wpisz liczbę całkowitą (-1, aby zakończyć): -1
Rysunek 19.2. Sekwencyjne przeszukiwanie tablicy w celu znalezienia elementu
Metoda linearSearch
Metoda linearSearch (wiersze od 9. do 18.) wykonuje wyszukiwanie liniowe. Metoda ta otrzymuje jako parametry tablicę do przeszukania (data) i klucz wyszukiwania (searchKey). Wiersze od 11. do 15. przechodzą przez elementy tablicy. Wiersz 12. porównuje każdy z nich z searchKey. Jeśli wartości są równe, wiersz 13. zwraca indeks elementu. Jeśli w tablicy istnieją duplikaty, wyszukiwanie zwróci pierwszy element tablicy pasujący do klucza wyszukiwania. Jeśli pętla zakończy się, nie znalazłszy wartości, wiersz 17. zwróci -1.
Metoda main
Metoda main umożliwia użytkownikowi wyszukanie wartości w tablicy. Wiersze od 24. do 28. tworzą tablicę z dziesięcioma elementami typu int i wypełniają ją losowymi wartościami z przedziału od 10 do 99. Wiersz 30. wyświetla zawartość
tablicy za pomocą metody statycznej toString klasy Arrays., która zwraca tekstową reprezentację tablicy jako listę oddzielonych przecinkami wartości zawartych w nawiasach kwadratowych ([ i ]). Wiersze 33. i 34. proszą użytkownika o wpisanie klucza wyszukiwania i go zapamiętują. Wiersz 38. wywołuje metodę linearSearch, aby określić, czy search Int znajduje się w tablicy data. Jeśli nie, linearSearch zwraca -1, a program informuje o tym użytkownika (wiersz 41.). Jeśli searchInt znajduje się w tablicy,
linearSearch zwraca położenie elementu, co program wyświetla w wierszach od 44. do 45. Wiersze od 49. do 50. pobierają od użytkownika następny klucz wyszukiwania.
Generowanie tablicy liczb losowych za pomocą strumienia Javy SE 8
Przypomnijmy, że możemy użyć metody ints z Secure Random do wygenerowania strumienia losowych wartości. Na rysunku 19.2
wiersze od 24. do 28. można zastąpić wierszem:
Pierwszy argument metody ints (10) określa liczbę elementów w strumieniu. Drugi i trzeci wskazują, że liczby losowe tworzone przez ints będą się mieściły w przedziale od 10 do 100, ale bez 100 (czyli od 10 do 99). Na wynikowym strumieniu IntStream wywołujemy metodę toArray, aby otrzymać tablicę int zawierającą 10 liczb losowych. W dalszych przykładach dla tego rozdziału wykorzystamy
tę technikę strumieniową zamiast pętli for do wypełniania elementów tablicy wartościami losowymi. Nadal będziemy korzystać z pętli for do wyświetlania wyników działania algorytmów wyszukiwania i sortowania.
Programowanie w Javie. Solidna wiedza w praktyce. Wydanie XI, Autorzy: Paul Deitel, Harvey Deitel, Wydawnictwo: Helion