Wyszukiwanie binarne – Algorytm typu „dziel i zwyciężaj”

Wyszukiwanie binarne to jeden z najpopularniejszych algorytmów do wyszukiwania danych w tablicy posortowanych liczb. Algorytm ten został oparty o metodę „dziel i zwyciężaj” dzięki czemu potrafi w czasie logarytmicznym znaleźć szukaną liczbę oraz zwrócić jej indeks jeśli oczywiście została odnaleziona. Dla przykładu przy tablicy liczb która zawiera milion elementów wyszukiwanie binarne do odnalezienia żądanej liczby potrzebuje wykonać zaledwie 20 porównań. Oczywiście aby to wszystko zadziałało przeszukiwana tablica musi zostać wcześniej posortowana.

Ogólna zasada działania algorytmu wyszukiwania binarnego polega na „dzieleniu” tablicy liczb na połowę i sprawdzaniu czy element znajdujący się dokładnie po środku jest elementem szukanym, jeśli nie to czy jest większy lub mniejszy. W ten sposób bardzo szybko zawężamy zakres poszukiwań, aż w końcu natrafimy na element który poszukujemy lub po prostu go nie znajdziemy. W pesymistycznym przypadku nasz program będzie miał złożoność czasową logn gdzie n to długość przeszukiwanej tablicy.

Przykładowa funkcja wyszukiwania binarnego napisana w języku Java operująca na tablicy o nazwie: tablicaLiczb:

public static int wyszukiwanieBinarne(int szukanaLiczba)
{
    int lewo = 0, prawo = tablicaLiczb.length - 1, srodek = 0;

    while(lewo <= prawo)
    {
        srodek = (lewo + prawo) / 2;
        if(tablicaLiczb[srodek] == szukanaLiczba)
            return srodek;
        else if(tablicaLiczb[srodek] < szukanaLiczba)
            lewo = srodek + 1;
        else
            prawo = srodek - 1;
    }

    return -1; //jeżeli liczba nie została odnaleziona zwróć -1
}

A co jeśli liczby w tablicy się powtarzają?

Ta podstawowa wersja algorytmu wyszukiwania binarnego sprawdza się wtedy kiedy na przykład dane występujące w tablicy nie powtarzają się lub nie interesuje nas ilość wystąpień szukanej liczby oraz indeks np. pierwszego lub ostatniego wystąpienia. Prosta modyfikacja algorytmu wyszukiwania binarnego pozwoli nam ominąć ten problem. Zamiast odnajdywania jakiegokolwiek elementu będziemy szukać jego pierwszego lub ostatniego wystąpienia.

Aby odnaleźć pierwsze wystąpienie danej liczby w tablicy będziemy wykorzystywać podstawową wersję algorytmu wyszukiwania binarnego ale kiedy już trafimy na szukany element to będziemy sprawdzać czy ten wcześniejszy o indeksie mniejszym o 1 też jest szukaną cyfrą. Jeżeli tak to musimy „przenieść się” do podzbioru na lewo wyznaczyć nowy środek i tak w kółko dopóki nie znajdziemy szukanego elementu przed którym nie będzie liczby którą szukamy. Oczywiście natrafienie na element o indeksie 0 kończy całą procedurę bowiem wiadomo iż wcześniej nie ma żadnych liczb.

Przykładowa implementacja przerobionej wersji algorytmu wyszukiwania binarnego służąca do znalezienia pierwszego wystąpienia szukanej liczby. Fragment programu (w całości dostępny jest na końcu tego artykułu) napisany w języku Java:

int lewo = 0, prawo = tablicaLiczb.length - 1, srodek = 0;
boolean czyZnalezione = false;
        
//WYSZUKIWANIE PIERWSZEGO POWTÓRZENIA DANEJ LICZBY
while(lewo <= prawo) 
{
    srodek = (lewo + prawo) / 2;
    if(tablicaLiczb[srodek] == szukanaLiczba) 
    {
        czyZnalezione = true;
        if(srodek == 0) break; //JEŻELI JEST TO PIERWSZY ELEMENT PRZERWIJ - WCZEŚNIEJ NIE MA ŻADNYCH LICZB
        if(tablicaLiczb[srodek - 1] == szukanaLiczba)
            prawo = srodek - 1;
        else
            break; //JEŻELI POPRZEDNI ELEMENT NIE JEST SZUKANĄ LICZBĄ PRZERWIJ
    } 
    else if(tablicaLiczb[srodek] < szukanaLiczba)
        lewo = srodek + 1; 
    else 
        prawo = srodek - 1;
}
        
int pierwszaLiczba = 0;
        
if(czyZnalezione) pierwszaLiczba = srodek;

Analogiczną procedurę zastosujemy do znalezienia ostatniego wystąpienia szukanej liczby tyle, że teraz zamiast przesuwać się na lewo będziemy przesuwali się w prawo, aż do momentu kiedy taki warunek: tablicaLiczb[i + 1] != szukanaLiczba, zostanie spełniony.

Przykładowy implementacja przerobionej wersji algorytmu wyszukiwania binarnego służąca do znalezienia ostatniego wystąpienia szukanej liczby. Fragment programu (w całości dostępny jest na końcu tego artykułu) napisany w języku Java:

lewo = 0; prawo = tablicaLiczb.length - 1; srodek = 0; 
czyZnalezione = false;
        
//WYSZUKIWANIE OSTATNIEGO POWTÓRZENIA DANEJ LICZBY
while(lewo <= prawo)
{      
    srodek = (lewo + prawo) / 2;
            
    if(tablicaLiczb[srodek] == szukanaLiczba) 
    {
        czyZnalezione = true;
        if (srodek == tablicaLiczb.length - 1) break; //JEŻELI JEST TO OSTATNI ELEMENT PRZERWIJ - DALEJ NIE MA JUŻ ŻADNYCH LICZB
        if (tablicaLiczb[srodek + 1] == szukanaLiczba) 
            lewo = srodek + 1;
        else 
            break; //JEŻELI NASTĘPNY ELEMENT NIE JEST SZUKANĄ LICZBĄ PRZERWIJ
    } 
    else if(tablicaLiczb[srodek] < szukanaLiczba) 
        lewo = srodek + 1;
    else 
        prawo = srodek - 1;
}
        
int ostatniaLiczba = 0;
if(czyZnalezione) ostatniaLiczba = srodek;

Teraz mając indeks pierwszego oraz ostatniego wystąpienia szukanej liczby można na przykład określić ilość jej powtórzeń.

Przykładowy program oparty o wyszukiwanie binarne zliczający ilość wystąpień danej liczby w posortowanej rosnąco tablicy (jeżeli szukana liczba nie występuje wypisywany jest komunikat: „Szukana liczba nie została odnaleziona.”):

import java.util.Scanner;

public class Source {
	
	public static int tablicaLiczb[];

    public static void main(String[] args) 
    {
        Scanner s = new Scanner(System.in);
        
        System.out.println("Podaj ilość zestawów danych: ");
        int iloscZestawowDanych = s.nextInt();
        
        for(int i = 0; i < iloscZestawowDanych; i++) 
        {
        	System.out.println("Podaj rozmiar tablicy z liczbami: ");
            int indeks = s.nextInt();
            
            tablicaLiczb = new int[indeks];
            
            System.out.println("Podaj liczby, które potem będą przeszukiwane (muszą one być posortowane od najmniejszej do największej): ");
            for(int j = 0; j < tablicaLiczb.length; j++)
                tablicaLiczb[j] = s.nextInt();
           
            System.out.println("Podaj ilość liczb jakich będziesz szukał: ");
            int iloscSzukanychLiczb = s.nextInt();
            
            System.out.println("Podaj liczbę, którą chcesz znaleźć: ");
            for (int j = 0; j < iloscSzukanychLiczb; j++) 
                szukaj(s.nextInt());
        }
    }

    public static void szukaj(int szukanaLiczba) 
    {
        int lewo = 0, prawo = tablicaLiczb.length - 1, srodek = 0;
        boolean czyZnalezione = false;
        
        //WYSZUKIWANIE PIERWSZEGO POWTÓRZENIA DANEJ LICZBY
        while(lewo <= prawo) 
        {
            srodek = (lewo + prawo) / 2;
            if(tablicaLiczb[srodek] == szukanaLiczba) 
            {
                czyZnalezione = true;
                if (srodek == 0) break; //JEŻELI JEST TO PIERWSZY ELEMENT PRZERWIJ - WCZEŚNIEJ NIE MA ŻADNYCH LICZB
                if (tablicaLiczb[srodek - 1] == szukanaLiczba)
                    prawo = srodek - 1;
                else
                    break; //JEŻELI POPRZEDNI ELEMENT NIE JEST SZUKANĄ LICZBĄ PRZERWIJ
            } 
            else if(tablicaLiczb[srodek] < szukanaLiczba)
                lewo = srodek + 1; 
            else 
                prawo = srodek - 1;
        }
        
        int pierwszaLiczba = 0;
        
        if(czyZnalezione) 
        	pierwszaLiczba = srodek;
        
        //CZYŚCIMY ZMIENNE ZE ŚMIECI
        lewo = 0; prawo = tablicaLiczb.length - 1; srodek = 0; czyZnalezione = false;
        
        //WYSZUKIWANIE OSTATNIEGO POWTÓRZENIA DANEJ LICZBY
        while(lewo <= prawo) {
      
            srodek = (lewo + prawo) / 2;
            
            if(tablicaLiczb[srodek] == szukanaLiczba) 
            {
                czyZnalezione = true;
                if(srodek == tablicaLiczb.length - 1) break; //JEŻELI JEST TO OSTATNI ELEMENT PRZERWIJ - DALEJ NIE MA JUŻ ŻADNYCH LICZB
                if(tablicaLiczb[srodek + 1] == szukanaLiczba) 
                    lewo = srodek + 1;
                else 
                    break; //JEŻELI NASTĘPNY ELEMENT NIE JEST SZUKANĄ LICZBĄ PRZERWIJ
            } 
            else 
                if(tablicaLiczb[srodek] < szukanaLiczba) 
                    lewo = srodek + 1;
                else 
                    prawo = srodek - 1;
        }
        
        int ostatniaLiczba = 0;
        if(czyZnalezione) ostatniaLiczba = srodek;
            
        if(czyZnalezione)
            System.out.println("Szukana liczba powtarza się: " + (ostatniaLiczba - pierwszaLiczba + 1) + " raz(y)."); //INDEKSY W TABLICY NUMEROWANE SĄ OD 0 WIĘC MUSIMY DODAĆ 1
        else
            System.out.println("Szukana liczba nie została odnaleziona.");
    }
}

Fot. (ilustracja wpisu): ideonexus.com, Flickr | CC.

Algorytm wyszukiwania binarnego, Algorytmy, Java, Programowanie, przeszukiwanie tablicy liczb, Wyszukiwanie binarne, wyszukiwanie liczb powtarzających się