Wyszukiwanie liniowe i binarne

Algorytmy: sortowanie i wyszukiwanie - Podstawy Javy (Java)

Wyszukiwanie liniowe (Linear Search): Przegląda kolejno wszystkie elementy tablicy Złożoność czasowa: O(n) Zalety: Działa na nieposortowanych tablicach Prosty w implementacji Wady: Nieefektywny dla dużych zbiorów danych Wyszukiwanie binarne (Binary Search): Wymaga posortowanej tablicy Złożoność czasowa: O(log n) Zalety: Bardzo efektywny dla dużych zbiorów Logarytmiczna złożoność Wady: Wymaga posortowanej tablicy Trudniejszy w implementacji Praktyczne zastosowania: Wyszukiwanie liniowe: Małe zbiory danych Nieposortowane dane Jednorazowe wyszukiwanie Wyszukiwanie binarne: Duże zbiory danych Często przeszukiwane dane Systemy bazodanowe

public class Main {
  public static void main(String[] args) {
    int[] array = {3, 8, 12, 15, 17, 21, 25, 29, 32, 37};  // tablica posortowana
    int target = 21;  // szukana wartość

    // Demonstracja wyszukiwania liniowego
    int linearResult = linearSearch(array, target);
    System.out.println("Wyszukiwanie liniowe: element " + target + 
      " znajduje się na pozycji " + linearResult);

    // Demonstracja wyszukiwania binarnego
    int binaryResult = binarySearch(array, target);
    System.out.println("Wyszukiwanie binarne: element " + target + 
      " znajduje się na pozycji " + binaryResult);
  }

  // Implementacja wyszukiwania liniowego
  public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == target) {
        return i;
      }
    }
    return -1;  // element nie został znaleziony
  }

  // Implementacja wyszukiwania binarnego
  public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
      int mid = (left + right) / 2;
      
      if (arr[mid] == target) {
        return mid;
      } else if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return -1;  // element nie został znaleziony
  }
}

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Podstawy Javy · Zaloguj się, aby zapisać postęp na koncie.