Tento tutoriál se naučí, jak můžeme použít binární vyhledávací algoritmus pomocí Pythonu k nalezení pozice indexu prvku v daném seznamu.

Úvod

Binární vyhledávání je algoritmus k nalezení určitého prvku v seznamu. Předpokládejme, že máme seznam tisíce prvků a potřebujeme získat pozici indexu konkrétního prvku. Pomocí binárního vyhledávacího algoritmu můžeme velmi rychle najít polohu indexu prvku.

Existuje mnoho vyhledávacích algoritmů, ale nejoblíbenější z nich je binární vyhledávání.

Prvky v seznamu musí být seřazeny, aby bylo možné použít binární vyhledávací algoritmus. Pokud prvky nejsou seřazeny, seřaďte je nejprve.

Pojďme pochopit koncept binárního vyhledávání.

Koncepce binárního vyhledávání

V binárním vyhledávacím algoritmu můžeme najít pozici prvku pomocí následujících metod.

• Rekurzivní metoda
• Iterativní metoda

Po technice přístupu rozděl a panuj následuje rekurzivní metoda. V této metodě se funkce volá znovu a znovu, dokud nenalezne prvek v seznamu.

Sada příkazů se několikrát opakuje, aby se našla pozice indexu prvku v iterační metodě. The zatímco K provedení tohoto úkolu se používá smyčka.

Binární vyhledávání je efektivnější než lineární, protože nepotřebujeme prohledávat každý index seznamu. Seznam musí být seřazen, aby se dosáhlo binárního vyhledávacího algoritmu.

Pojďme krok za krokem implementovat binární vyhledávání.

Máme seřazený seznam prvků a hledáme pozici indexu 45.

[12, 24, 32, 39, 45, 50, 54]

V našem seznamu tedy nastavujeme dva ukazatele. Jeden ukazatel se používá k označení menší hodnoty nízký a druhý ukazatel se používá k označení nejvyšší volané hodnoty vysoký .

Dále vypočítáme hodnotu střední prvek v poli.

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer) 

Nyní porovnáme hledaný prvek se střední hodnotou indexu. V tomto případě, 32 se nerovná Čtyři pět. Musíme tedy provést další srovnání, abychom prvek našli.

Pokud se číslo, které hledáme, rovná středu. Pak se vraťte střední jinak přejděte k dalšímu srovnání.

Číslo, které se má vyhledat, je větší než střední číslo, porovnáme n se středním prvkem prvků na pravé straně střední a nastavte nízkou hodnotu nízká = střední + 1.

V opačném případě porovnejte n s střední prvek prvků na levé straně střední a nastavit vysoký na vysoká = střední - 1.

Opakujte, dokud nenajdete číslo, které hledáme.

Implementujte binární vyhledávání v Pythonu

Nejprve implementujeme binární vyhledávání iterační metodou. Zopakujeme sadu příkazů a iterujeme každou položku seznamu. Prostřední hodnotu najdeme, dokud nebude vyhledávání dokončeno.

Pojďme pochopit následující program iterační metody.

Implementace Pythonu

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

Vysvětlení:

Ve výše uvedeném programu -

• Vytvořili jsme funkci tzv binární_hledání() funkce, která má dva argumenty - seznam k seřazení a číslo, které se má prohledávat.
• Deklarovali jsme dvě proměnné pro uložení nejnižší a nejvyšší hodnoty v seznamu. Low je přiřazena počáteční hodnota 0, vysoký na len(seznam1) - 1 a střední jako 0.
• Dále jsme vyhlásili zatímco smyčka s podmínkou, že Nejnižší je stejný a menší než nejvyšší Cyklus while se bude opakovat, pokud číslo ještě nebylo nalezeno.
• V cyklu while najdeme střední hodnotu a porovnáme hodnotu indexu s číslem, které hledáme.
• Pokud je hodnota středního indexu menší než n , zvýšíme střední hodnotu o 1 a přiřadíme ji k Hledání se přesune na levou stranu.
• V opačném případě snižte střední hodnotu a přiřaďte ji k vysoký . Vyhledávání se přesune na pravou stranu.
• Pokud se n rovná střední hodnotě, vraťte se střední .
• To se bude dít až do nízký je stejný a menší než vysoký .
• Pokud se dostaneme na konec funkce, pak prvek není v seznamu přítomen. Volající funkci vrátíme -1.

Pojďme pochopit rekurzivní metodu binárního vyhledávání.

Rekurzivní binární vyhledávání

V binárním vyhledávání lze použít metodu rekurze. V tomto budeme definovat rekurzivní funkci, která se sama volá, dokud nesplní podmínku.

ipconfig pro ubuntu

Pojďme pochopit výše uvedený program pomocí rekurzivní funkce.

Program Python

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1') 

Výstup:

 Element is present at index 2 

Vysvětlení

Výše uvedený program je podobný předchozímu programu. Deklarovali jsme rekurzivní funkci a její základní podmínku. Podmínkou je, že nejnižší hodnota je menší nebo rovna nejvyšší hodnotě.

• Prostřední číslo vypočítáme jako v minulém programu.
• Použili jsme -li příkaz pokračovat v binárním vyhledávání.
• Pokud je střední hodnota rovna číslu, které hledáme, je vrácena střední hodnota.
• Pokud je střední hodnota menší než hodnota, hledáme naši rekurzivní funkci binární_hledání() znovu a zvyšte střední hodnotu o jednu a přiřaďte nízké.
• Pokud je střední hodnota větší než hodnota, kterou hledáme, pak naše rekurzivní funkce binární_hledání() znovu a snižte střední hodnotu o jednu a přiřaďte ji nízké.

V poslední části jsme napsali náš hlavní program. Je stejný jako předchozí program, ale jediný rozdíl je v tom, že jsme předali dva parametry v binární_hledání() funkce.

Je to proto, že v rekurzivní funkci nemůžeme přiřadit počáteční hodnoty nízkým, vysokým a středním hodnotám. Pokaždé, když je zavolána rekurzivní, bude hodnota těchto proměnných resetována. To dá špatný výsledek.

Složitost

Složitost binárního vyhledávacího algoritmu je O(1) pro lepší případ. To se stane, pokud prvek, který hledáme, najdeme v prvním srovnání. The O(logn) je nejhorší a průměrná složitost binárního vyhledávání. To závisí na počtu vyhledávání, které se provádí za účelem nalezení prvku, který hledáme.

Závěr

Binární vyhledávací algoritmus je nejúčinnějším a nejrychlejším způsobem vyhledávání prvku v seznamu. Přeskočí to zbytečné srovnání. Jak název napovídá, vyhledávání je rozděleno na dvě části. Zaměřuje se na stranu seznamu, která se blíží číslu, které hledáme.

Probrali jsme oba způsoby, jak najít pozici indexu daného čísla.