Jedním z nejzákladnějších algoritmů v informatice je algoritmus Binary Search. Binární vyhledávání můžete implementovat pomocí dvou metod: iterační metody a rekurzivní metody. Zatímco obě metody mají stejnou časovou složitost, iterativní metoda je mnohem efektivnější z hlediska prostorové složitosti.

Iterační metoda má prostorovou složitost O(1) ve srovnání s O(logn) vyrobené rekurzivní metodou. Jak tedy můžete implementovat algoritmus binárního vyhledávání pomocí iterační metody v C, C++ a Pythonu?

Co je binární vyhledávání?

Binární vyhledávání známé také jako půlintervalové vyhledávání, logaritmické vyhledávání nebo binární sekání je algoritmus, který vyhledává a vrací pozici prvku v seřazeném poli. Vyhledávací prvek je porovnán se středním prvkem. Vezmeme-li průměr dolní a horní meze, můžete najít střední prvky.

Pokud je hledaný prvek větší než prostřední prvek, znamená to, že všechny prvky na levé straně jsou menší než hledaný prvek. Ovládací prvek se tedy přesune na pravou stranu pole (pokud je pole ve vzestupném pořadí) zvýšením spodního limitu na další pozici prostředního prvku.

instagram viewer

Podobně, pokud je vyhledávací prvek menší než prostřední prvek, znamená to, že všechny prvky na pravé straně jsou větší než vyhledávací prvek. Ovládací prvek se tedy přesune do levé části pole změnou horního limitu na předchozí pozici prostředního prvku.

To výrazně snižuje počet srovnání ve srovnání s implementace lineárního vyhledávání kde se počet srovnání rovná počtu prvků v nejhorším scénáři. Tato metoda je velmi užitečná při hledání čísel v telefonním seznamu nebo slov ve slovníku.

Zde je schematické znázornění Binární vyhledávací algoritmus:

Binární vyhledávání pomocí C

Chcete-li implementovat binární vyhledávání pomocí jazyka C, postupujte takto:

Celý zdrojový kód programu Binary Search Program využívající C, C++, Java a Python je přítomen v tomto úložiště GitHub.

Program definuje funkci, binární vyhledávání (), který vrací buď index nalezené hodnoty nebo -1 pokud není přítomen:

#zahrnout <stdio.h>
intbinární vyhledávání(int arr[], int arr_size, int vyhledávací_číslo){
/*... */
}

Funkce funguje tak, že se iterativně zužuje vyhledávací prostor. Protože binární vyhledávání funguje na seřazených polích, můžete vypočítat střed, který jinak nedává smysl. Můžete buď požádat uživatele o seřazené pole, nebo použít třídicí algoritmy, jako je Bubble nebo Selection sort.

The nízký a vysoký proměnné ukládají indexy, které představují hranice aktuálního vyhledávacího prostoru. střední ukládá index uprostřed:

int nízká = 0, vysoká = arr_size - 1, střední;

Hlavní zatímco() smyčka zúží vyhledávací prostor. Pokud se hodnota nízkého indexu někdy stane vyšší než horní index, pak byl vyhledávací prostor vyčerpán, takže hodnota nemůže být přítomna.

zatímco (nízká <= vysoká) {
/* pokračuje... [1] */
 }
vrátit se-1;

Po aktualizaci středního bodu na začátku cyklu existují tři možné výsledky:

  1. Pokud je hodnota ve středu ta, kterou hledáme, vraťte tento index.
  2. Pokud je střední hodnota větší než ta, kterou hledáme, snižte nejvyšší hodnotu.
  3. Pokud je střední hodnota nižší, zvyšte dolní. 
/* [1] ...pokračování */
 střední = (nízká + (vysoká - nízká)) / 2;
if (arr[mid] == search_number)
vrátit se střední;
jiný-li (arr[mid] > search_number)
 vysoká = střední - 1;
jiný
 nízká = střední + 1;

Otestujte funkci pomocí uživatelského vstupu. Použití scanf() získat vstup z příkazového řádku, včetně velikosti pole, jeho obsahu a čísla, které chcete vyhledat:

inthlavní(){
int arr[100], i, arr_size, search_number;
 printf("Zadejte počet prvků: ");
 scanf("%d", &arr_size);
 printf("Zadejte prosím čísla: ");
pro (i = 0; i < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Zadejte číslo, které chcete vyhledat: ");
 scanf("%d", &hledané_číslo);


i = binarySearch (arr, arr_size, search_number);


jestliže (i==-1)
 printf("Číslo není k dispozici");
jiný
 printf("Číslo je na pozici %d"i + 1);
vrátit se0;
}

Pokud číslo najdete, zobrazte jeho pozici nebo index, jinak se zobrazí zpráva, že číslo není přítomno.

Binární vyhledávání pomocí C++

Program C můžete převést na program C++ importem souboru Vstupní výstupní proud a použijte jmenný prostor std abyste se vyhnuli opakovanému opakování v průběhu programu.

#zahrnout <iostream>
použitím jmenný prostorstd;

Použití cout s obsluhou odsávání << namísto printf() a cin s operátorem vkládání >> namísto scanf() a váš program v C++ je připraven.

printf("Zadejte počet prvků: ");
cout <<"Zadejte počet prvků: ";
scanf("%d", &arr_size);
cin >> arr_size;

Binární vyhledávání pomocí Pythonu

Protože Python nemá vestavěnou podporu pro pole, použijte seznamy. Definujte funkci, binární vyhledávání (), který přijímá tři parametry, seznam, jeho velikost a číslo, které se má hledat:

defbinární vyhledávání(arr, arr_size, search_number):
 nízká = 0
 high = arr_size - 1
zatímco nízká <= vysoká:
 střední = nízký + (vysoký-nízký)//2
 if arr[mid] == search_number:
vrátit se střední
elif arr[mid] > search_number:
 vysoká = střední - 1
jiný:
 nízká = střední + 1
vrátit se-1

Inicializovat dvě proměnné, nízký a vysoký, který bude sloužit jako spodní a horní mez seznamu. Podobně jako v implementaci C použijte a zatímco smyčka, která zužuje vyhledávací prostor. Inicializovat střední pro uložení střední hodnoty seznamu. Python poskytuje operátor dělení podlahy (//), který poskytuje největší možné celé číslo.

Proveďte srovnání a zužte vyhledávací prostor tak, aby se střední hodnota rovnala číslu vyhledávání. Pokud vyhledávací číslo není k dispozici, ovládací prvek se vrátí -1.

arr_size = int (vstup("Zadejte počet prvků: "))
arr=[]
tisk("Zadejte prosím čísla: ", konec="")
pro i v rozsahu (0, arr_size):
 arr.append(int(vstup()))
hledané_číslo = int (vstup("Zadejte číslo, které chcete vyhledat: "))
výsledek = binarySearch (arr, arr_size, search_number)
pokud výsledek == -1:
 tisk("Číslo není k dispozici")
jiný:
 tisk ("Číslo je přítomen na pozici ", (výsledek + 1))

Otestujte funkci pomocí uživatelského vstupu. Použití vstup() získat velikost seznamu, jeho obsah a číslo, které chcete vyhledat. Použití int() přetypovat vstup řetězce akceptovaný Pythonem jako výchozí na celé číslo. Chcete-li přidat čísla do seznamu, použijte připojit() funkce.

Volání binární vyhledávání () a předat argumenty. Pokud číslo najdete, zobrazte jeho pozici nebo index, jinak se zobrazí zpráva, že číslo není přítomno.

Výstup binárního vyhledávacího algoritmu

Když je prvek přítomen v poli, následuje výstup algoritmu Binary Search:

Následující je výstup algoritmu binárního vyhledávání, když prvek není přítomen v poli:

Naučte se základní datové struktury a algoritmy

Vyhledávání je jedním z prvních algoritmů, které se naučíte, a často se na něj ptají v soutěžích o kódování, umístění a pohovorech. Mezi další algoritmy, které byste se měli naučit, patří třídění, hašování, dynamické programování, porovnávání řetězců a algoritmy testování primality.

Kromě toho je nezbytné porozumět časové a prostorové složitosti algoritmů. Jsou jedním z nejdůležitějších konceptů v informatice při určování účinnosti jakéhokoli algoritmu. Se znalostí datových struktur a algoritmů jste povinni vytvořit ty nejlepší programy.