Wyszukiwanie binarne

Wyszukiwanie binarne optymalizuje algorytm poszukiwań do kilku kroków. Opiera się ono na podziale tablicy na dwie części i sprawdzeniu czy szukana wartość znajduje się na środku czy też jest mniejsza lub też większa od elementu środkowego. W zależności od wyniku szukamy dalej w lewej bądź też prawej części tablicy. Taki sposób jest analogiczny do wyszukiwania danych w książce telefonicznej czy też słowniku. Oczywiście tablica, w której szukamy musi być posortowana (w przykładzie wykorzystamy sortowanie przez wybieranie). Chcemy napisać metodę która umożliwi nam w sposób rekurencyjny odnalezienie w tablicy konkretnej wartości.

// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Wyszukiwanie binarne
 * @author kodatnik.blogspot.com 
 */ 
public class WyszukiwanieBinarne {
 
 // metoda sortuje elementy tablicy przekazanej jako parametr
 public static void sortowaniePrzezWybieranie(int[] wejscie) {
  // zmienna przechowująca rozmiar tablicy
  int rozmiarTablicy = wejscie.length;
  
  // pętla przejścia przez wszystkie elementy tablicy
  for (int i = 0; i < rozmiarTablicy; i++){
   // zakladamy, ze element na pozycji i jest najmniejszy
   int min = wejscie[i];
   // zapisujemy indeks tego elementu
   int indeks = i;
   
   // szukamy w pozostałej części tablicy elementu mniejszego niz min
   for (int j = i; j < rozmiarTablicy; j++){
    // jesli jest taki, on staje się teraz elementam najmniejszym
    if(wejscie[j] < min) {
     min = wejscie[j];
     // zapisujemy jego indeks
     indeks=j;
    }
   }
   // zamieniamy miejscami elementy w tablicy 
   // najmniejszy z aktualnym wskazywanym przez zmienną i
   wejscie[indeks] = wejscie[i];
   wejscie[i] = min;
  }
 }

 // metoda rekurencyjna szukająca w podanej jako parametr tablicy (od indeksu poczatek do indeksu koniec) wartości
 // zwraca -1 jeśli szukana wartość nie występuje, lub indeks pierwszego wystąpienia szukanej wartości
 // przekazana jako parametr tablica musi być wcześniej posortowana
 public static int szukajBinarnie(int[] wejscie, int poczatek, int koniec, int szukana) {

  // sprawdzamy czy przekazana tablica nie jest jednoelementowa
  if( poczatek == koniec) {
   // jeśli tak sprawdzamy czy element nie jest tym, którego szukamy (zwracamy indeks elementu, lub -1)
   if (wejscie[poczatek] == szukana) return poczatek;
   else return -1;
  }

  if( poczatek > koniec)
   // jeśli poczatek jest większy od końca kończymy wyszukiwanie zwracając -1
   return -1;  
  
  // dzielimy tablicę na dwie części
  int srodek = (poczatek+koniec)/2;
 
  // sprawdzamy czy element środkowy nie jest szukanym (jeśli tak zwracamy jego indeks)
  if(wejscie[srodek] == szukana) return srodek;

  // jeśli nie, wywołujemy rekurencyjnie naszą metodę dla prawej bądź też lewej części tablicy
  if(wejscie[srodek] > szukana) return szukajBinarnie(wejscie, poczatek, srodek-1, szukana);
  else return szukajBinarnie(wejscie, srodek+1, koniec, szukana);
 }
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę nieposortowaną na ekranie
  System.out.print ("Tablica nieposortowana: " );
  pokazTablice(tablica);  
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Jaką wartość chcesz znaleźć w tablicy: " );

  // pobieramy od użytkownika liczbę
  int liczba = sc.nextInt();    

  // sortujemy tablicę
  sortowaniePrzezWybieranie(tablica);  
  
  // wyświetlamy tablicę posortowaną na ekranie
  System.out.print ("Tablica posortowana: " );
  pokazTablice(tablica);
  
  // wywołujemy metodę oraz zapisujemy to co zwróci
  int wynik = szukajBinarnie(tablica, 0, tablica.length-1, liczba);
  
  // jeśli wynik jest różny od -1 wyświetlamy informacje o indeksie, na którym została znaleziona wartość
  if (wynik != -1) System.out.println ("Liczba " + liczba + " została znaleziona w tablicy na indeksie: " + wynik);
  else System.out.println ("Liczba " + liczba + " nie została znaleziona w tablicy.");
 }
}

Uruchomiona aplikacja (wartość znaleziona):

Tablica nieposortowana: 4 6 1 2 3 8 7 9 5 
Jaką wartość chcesz znaleźć w tablicy: 3
Tablica posortowana: 1 2 3 4 5 6 7 8 9 
Liczba 3 została znaleziona w tablicy na indeksie: 2

Uruchomiona aplikacja (wartość nie znaleziona):

Tablica nieposortowana: 4 6 1 2 3 8 7 9 5 
Jaką wartość chcesz znaleźć w tablicy: 17
Tablica posortowana: 1 2 3 4 5 6 7 8 9 
Liczba 17 nie została znaleziona w tablicy.