Jednym z najbardziej podstawowych algorytmów w informatyce jest algorytm wyszukiwania binarnego. Wyszukiwanie binarne można zaimplementować przy użyciu dwóch metod: metody iteracyjnej i metody rekurencyjnej. Chociaż obie metody mają taką samą złożoność czasową, metoda iteracyjna jest znacznie bardziej wydajna pod względem złożoności przestrzennej.
Metoda iteracyjna ma złożoność przestrzenną ok O(1) w porównaniu do O(logowanie) tworzony metodą rekurencyjną. Jak więc zaimplementować algorytm wyszukiwania binarnego przy użyciu metody iteracyjnej w językach C, C++ i Python?
Co to jest wyszukiwanie binarne?
Wyszukiwanie binarne, znane również jako wyszukiwanie w połowie przedziału, wyszukiwanie logarytmiczne lub przecinanie binarne, to algorytm, który wyszukuje i zwraca pozycję elementu w posortowanej tablicy. Element wyszukiwania jest porównywany z elementem środkowym. Biorąc średnią z dolnej i górnej granicy, możesz znaleźć środkowe elementy.
Jeśli element wyszukiwania jest większy niż element środkowy, oznacza to, że wszystkie elementy po lewej stronie są mniejsze niż element wyszukiwania. Tak więc kontrolka przesuwa się na prawą stronę tablicy (jeśli tablica jest w porządku rosnącym) poprzez zwiększenie dolnego limitu do następnej pozycji środkowego elementu.
Podobnie, jeśli element wyszukiwania jest mniejszy niż element środkowy, oznacza to, że wszystkie elementy po prawej stronie są większe niż element wyszukiwania. Tak więc sterowanie przesuwa się do lewej części tablicy, zmieniając górną granicę na poprzednią pozycję środkowego elementu.
Zmniejsza to drastycznie liczbę porównań w porównaniu do implementacja wyszukiwania liniowego gdzie liczba porównań jest równa liczbie elementów w najgorszym przypadku. Ta metoda okazuje się bardzo przydatna do wyszukiwania numerów w książce telefonicznej lub słów w słowniku.
Oto schematyczne przedstawienie tzw Algorytm wyszukiwania binarnego:
Wyszukiwanie binarne za pomocą C
Wykonaj następujące kroki, aby zaimplementować wyszukiwanie binarne przy użyciu C:
Obecny jest w nim cały kod źródłowy Binary Search Program używający C, C++, Java i Python Repozytorium GitHub.
Program definiuje funkcję, wyszukiwanie binarne(), która zwraca indeks znalezionej wartości lub -1 jeśli go nie ma:
#włączać <stdio.h>
intwyszukiwanie binarne(int arr [], int arr_size, int numer_wyszukiwania){
/*... */
}
Funkcja działa poprzez iteracyjne zawężanie przestrzeni wyszukiwania. Ponieważ wyszukiwanie binarne działa na posortowanych tablicach, możesz obliczyć środek, co w przeciwnym razie nie ma sensu. Możesz poprosić użytkownika o posortowaną tablicę lub użyć algorytmów sortowania, takich jak sortowanie bąbelkowe lub wybieranie.
The Niski I wysoki zmienne przechowują indeksy reprezentujące granice bieżącej przestrzeni wyszukiwania. Środek przechowuje indeks w środku:
int niski = 0, wysoki = arr_size - 1, Środek;Główny chwila() pętla zawęzi przestrzeń wyszukiwania. Jeśli wartość niskiego indeksu kiedykolwiek stanie się większa niż górnego indeksu, oznacza to, że przestrzeń wyszukiwania została wyczerpana, więc wartość nie może być obecna.
chwila (niski <= wysoki) {
/* trwa... [1] */
}
powrót-1;
Po zaktualizowaniu punktu środkowego na początku pętli są trzy możliwe wyniki:
- Jeśli wartość w punkcie środkowym jest tą, której szukamy, zwróć ten indeks.
- Jeśli wartość punktu środkowego jest większa niż ta, której szukamy, zmniejsz maksimum.
- Jeśli wartość punktu środkowego jest mniejsza, zwiększ dolną.
/* [1] ...ciąg dalszy */
średni = (niski + (wysoki - niski)) / 2;
if (arr[mid] == search_number)
powrót Środek;
w przeciwnym razieJeśli (arr[mid] > search_number)
wysoki = średni - 1;
w przeciwnym razie
niski = średni + 1;
Przetestuj funkcję za pomocą danych wprowadzonych przez użytkownika. Używać skanf() aby uzyskać dane wejściowe z wiersza poleceń, w tym rozmiar tablicy, jej zawartość i liczbę do wyszukania:
intgłówny(){
int arr[100], i, arr_size, search_number;
printf("Podaj ilość elementów: ");
skanf("%D", &arr_size);
printf("Proszę wpisać liczby: ");dla (i = 0; I < arr_size; i++) {
skanf("%D", &arr[i]);
}printf("Podaj numer do wyszukania: ");
skanf("%D", &numer_wyszukiwania);i = binarySearch (arr, arr_size, search_number);
jeśli (i==-1)
printf("Brak numeru");
w przeciwnym razie
printf("Liczba jest obecna na pozycji %d", ja + 1);
powrót0;
}
Jeśli znajdziesz numer, wyświetl jego pozycję lub indeks, w przeciwnym razie pojawi się komunikat o braku numeru.
Wyszukiwanie binarne przy użyciu C++
Możesz przekonwertować program C na program C++, importując plik Strumień wejściowy i wyjściowy I użyj standardowej przestrzeni nazw aby uniknąć powtarzania go wiele razy w trakcie programu.
#włączać <iostream>
za pomocą przestrzeń nazwstandardowe;Używać cout z operatorem ekstrakcji << zamiast printf() I cin z operatorem wstawiania >> zamiast skanf() i twój program C++ jest gotowy.
printf("Podaj ilość elementów: ");
cout <<"Podaj ilość elementów: ";
skanf("%D", &arr_size);
cin >> arr_size;Wyszukiwanie binarne przy użyciu Pythona
Ponieważ Python nie ma wbudowanej obsługi tablic, użyj list. Zdefiniuj funkcję, wyszukiwanie binarne(), który akceptuje trzy parametry, listę, jej rozmiar i liczbę do wyszukania:
pokwyszukiwanie binarne(arr, arr_size, search_number):
niski = 0
wysoki = arr_size - 1
chwila niski <= wysoki:
średni = niski + (wysoki-niski)//2
if arr[mid] == numer_wyszukiwania:
powrót Środek
Elif arr[mid] > szukaj_numer:
wysoki = średni - 1
w przeciwnym razie:
niski = średni + 1
powrót-1Zainicjuj dwie zmienne, Niski I wysoki, aby służyć jako dolna i górna granica listy. Podobnie jak w przypadku implementacji C, użyj a chwila pętla, która zawęża przestrzeń wyszukiwania. Zainicjuj Środek do przechowywania środkowej wartości listy. Python udostępnia operator dzielenia pięter (//), który zapewnia największą możliwą liczbę całkowitą.
Dokonaj porównań i zawęź obszar wyszukiwania, aż wartość środkowa będzie równa liczbie wyszukiwania. Jeśli szukany numer nie jest obecny, sterowanie powróci -1.
arr_size = int (input("Podaj ilość elementów: "))
arr=[]
wydrukować("Proszę wpisać liczby: ", koniec="")
dla i w zakresie (0,arr_size):
arr.append(int(wejście()))
numer_wyszukiwania = int (input("Podaj numer do wyszukania: "))
wynik = binarySearch (arr, arr_size, search_number)
jeśli wynik == -1:
wydrukować("Brak numeru")
w przeciwnym razie:
print("Liczba Jest obecny na pozycji ", (wynik + 1))Przetestuj funkcję za pomocą danych wprowadzonych przez użytkownika. Używać wejście() aby uzyskać rozmiar listy, jej zawartość i numer do wyszukania. Używać int() aby wpisać ciąg wejściowy akceptowany przez Pythona jako domyślny na liczbę całkowitą. Aby dodać numery do listy, użyj dodać() funkcjonować.
Dzwonić wyszukiwanie binarne() i przekazać argumenty. Jeśli znajdziesz numer, wyświetl jego pozycję lub indeks, w przeciwnym razie pojawi się komunikat o braku numeru.
Dane wyjściowe algorytmu wyszukiwania binarnego
Poniżej przedstawiono dane wyjściowe algorytmu wyszukiwania binarnego, gdy element jest obecny w tablicy:
Poniżej przedstawiono dane wyjściowe algorytmu wyszukiwania binarnego, gdy elementu nie ma w tablicy:
Poznaj podstawowe struktury danych i algorytmy
Wyszukiwanie jest jednym z pierwszych algorytmów, których się uczysz i często jest ono zadawane w konkursach kodowania, stażach i rozmowach kwalifikacyjnych. Niektóre inne algorytmy, których powinieneś się nauczyć, to algorytmy sortowania, mieszania, programowania dynamicznego, dopasowywania ciągów i testowania pierwszorzędności.
Ponadto niezbędne jest zrozumienie złożoności czasowej i przestrzennej algorytmów. Są jednym z najważniejszych pojęć w informatyce przy określaniu wydajności dowolnego algorytmu. Dzięki znajomości struktur danych i algorytmów z pewnością zbudujesz najlepsze programy.
