Wyszukiwanie binarne

binary search

Czy kiedykolwiek zastanawialiście się, jak w gąszczu milionów, a czasem wręcz miliardów rekordów!
– znajduje się to, czego akurat teraz szukacie?

To właśnie tam, w zakamarkach wyszukiwania binarnego, tkwi sekret szybkiego i efektywnego odnajdywania informacji.
Odkryjmy zatem świat tego potężnego narzędzia, które stanowi fundament wielu zaawansowanych algorytmów wyszukiwania danych.

Wyszukiwanie binarne – wprowadzenie

Z tego materiału dowiesz się:

  • Czym jest wyszukiwanie binarne?
  • Jakie ma zastosowanie wyszukiwanie binarne?
  • Jak działa mechanizm wyszukiwania binarnego?
  • Jak zaimplementować algorytm wyszukiwania binarnego?

Wyszukiwanie binarne

Wyszukiwanie binarne – zwane również „podziałem na pół”, to algorytm, który w bardzo efektywny sposób odnajduje poszukiwany element w posortowanym zbiorze danych. Ta pozornie trywialna idea sprawia, że algorytm ten doskonale sprawdza się w praktyce, szczególnie przy dużych ilościach danych.

Wyszukiwanie binarne – mechanizm działania

Wyszukiwanie binarne, opiera się na zasadzie dzielenia zbioru na pół. Następnie, w każdym kroku eliminujemy jedną połowę danych, skupiając się na drugiej.
To proste podejście sprawia, że algorytm jest zarówno łatwy do zrozumienia, jak i niezwykle efektywny.

Środek aktualnie rozpatrywanego zbioru staje się punktem odniesienia. Porównujemy poszukiwaną wartość z elementem środkowym i na podstawie wyniku decydujemy, czy kontynuować poszukiwania w lewej, czy prawej połowie zbioru.

Każde porównanie skutkuje eliminacją jednej połowy danych. To kluczowe działanie sprawia, że nawet w dużych zbiorach proces poszukiwania jest niezwykle szybki. Eliminujemy niepotrzebne elementy, skupiając się coraz bardziej na obszarze, gdzie prawdopodobnie znajduje się szukana wartość.

Proces dzielenia i porównywania powtarza się, aż dojdziemy do jednego elementu, który będzie równy poszukiwanej wartości. To powtarzalne działanie sprawia, że algorytm jest skalowalny i efektywny niezależnie od rozmiaru danych.

binary search, wyszukiwanie binarne

Wyszukiwanie binarne – warianty i zastosowanie

Wyszukiwanie binarne to nie tylko jednorazowe narzędzie
– posiada różne warianty i znajduje zastosowanie w różnych obszarach programowania.
Oto tylko niektóre z nich:

  • Wyszukiwanie binarne w niesortowanych danych
    – Chociaż tradycyjne wyszukiwanie binarne działa tylko w przypadku posortowanych danych, istnieją modyfikacje algorytmu, które pozwalają na wyszukiwanie w nieposortowanych zbiorach. Tego typu warianty wymagają jednak bardziej złożonych kroków i zazwyczaj są mniej efektywne.
  • Wyszukiwanie binarne dla typów obiektowych
    Algorytm ten nie jest ograniczony do poszukiwania w zbiorach liczb całkowitych. Dla typów obiektowych można dostosować porównania, aby szukać konkretnego obiektu w posortowanym zbiorze.
  • Wyszukiwanie binarne w bazach danych
    Wyszukiwanie rekordów spełniających określone kryteria może być optymalizowane przy użyciu tego algorytmu, zwłaszcza gdy dane są indeksowane.
  • Wyszukiwanie binarne w grach komputerowych
    – W grach komputerowych, algorytm ten często jest wykorzystywany do przyspieszania procesów wyszukiwania, np. w poszukiwaniu obiektów w przestrzeni trójwymiarowej lub wykonywaniu interakcji z elementami gry.

Wyszukiwanie binarne – algorytm

Zobaczmy teraz implementację iteracyjnego wyszukiwania binarnego w języku Java. Warto zauważyć, że przed przystąpieniem do implementacji takiego algorytmu w rzeczywistym projekcie, ważne jest upewnienie się, że dane są posortowane, co jest warunkiem koniecznym dla poprawnego działania tego algorytmu.

static int binarySearch(int arr[], int target) {
	int low = 0, high = arr.length - 1;

	while (low <= high) {
		int mid = low + (high - low) / 2;

		// Sprawdź, czy target znajduje się w środku
		if (arr[mid] == target) {
			return mid;
		}


		// Jeśli target jest mniejszy, ignoruj prawą połowę
		if (arr[mid] > target) {
			high = mid - 1;

			// Jeśli target jest większy, ignoruj lewą połowę
		} else {
			low = mid + 1;
		}
	}

	// Jeśli target nie jest obecny w tablicy
	return -1;
}

Wewnętrzne implementacje algorytmu wyszukiwanie binarne w języku Java są dostępne chociażby w klasie Arrays lub Collections.

        Arrays.binarySearch(int[] a, int key)
        Collections.binarySearch(List<? extends Comparable<? super T>> list, T key)

Java – wyszukiwanie binarne – podsumowanie

Wyszukiwanie binarne (ang. binary search) – to potężne narzędzie, szczególnie skuteczne w poszukiwaniu w posortowanych danych. Algorytm ten znajduje szerokie zastosowanie w praktyce programistycznej, od baz danych po gry komputerowe. Wyszukiwanie binarne znalazło swoje miejsce w implementacjach wewnętrznych w języku Java, co podkreśla jego wszechstronność i użyteczność w różnych kontekstach programistycznych.


20+ BONUSOWYCH materiałów z programowania

e-book – „8 rzeczy, które musisz wiedzieć, żeby dostać pracę jako programista”,
e-book – „Java Cheat Sheet”,
checklista – „Pytania rekrutacyjne”
i wiele, wiele wiecej!

Jak zostać programistą

No comments
Share:

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *