Az elemek gyűjteményét két részre osztjuk a Bináris keresésben, hogy csökkentsük az elemek felfedezéséhez szükséges közvetlen összehasonlítások számát. Van azonban egy követelmény: a tömb elemeit előzetesen rendezni kell.

Bináris keresés

A Bináris keresés A metódus megkeresi egy adott listatag indexét. A legnépszerűbb és leggyorsabb algoritmusok közé tartozik. A bináris keresési eljárás működéséhez a lista bejegyzéseit rendezni kell.

Bináris keresés egy hatékonyabb keresési technika egy elem indexének megtalálására, mint Lineáris keresés hiszen nem kell minden listaindexet megvizsgálnunk.

A bináris keresési algoritmus teljes művelete a következő lépésekben foglalható össze:

• Keresse meg a rendezett tömb középső elemét.
• Hasonlítsa össze az elhelyezendő elemet a középső elemmel.
• Ha ez az elem egyenlő az adott lista középső elemével, akkor a középső elem indexe kerül visszaadásra. Ellenkező esetben az algoritmus összehasonlítja az elemet a középen lévő elemmel.
• Most, ha az elhelyezendő elem nagyobb, mint a lista középső eleme, akkor azt a lista jobb feléhez, azaz a középső index utáni elemekkel fogja összehasonlítani.
• Vagy ha az elem kisebb, mint a lista közepén lévő elem, akkor csak a lista bal felével, azaz a középső index előtti elemekkel kerül összehasonlításra.

Rekurzív bináris keresés

A bináris keresés azt jelenti, hogy a keresési intervallumot folyamatosan 2 egyenlő részre osztják, hogy egy elemet megtaláljanak egy rendezett tömbben, az ismétlődő bináris keresés pedig a teljes bináris keresési eljárás kisebb kérdésekre való felosztását jelenti. A rekurzív bináris keresés a bináris keresés rekurziós válasza.

Az alábbiak azok a jellemzők, amelyeknek a teljesen rekurzív megoldásoknak meg kell felelniük:

1. A rekurzív megközelítéshez alapeset szükséges.
2. A rekurzív megközelítésben rekurzív tesztesetnek kell lennie.
3. A rekurzív megközelítésnek közelebb kell kerülnie az alapesethez.

Egy bonyolult probléma legalacsonyabb felosztását egy alapeset képviseli, amely végső eset. Tehát a bináris keresés rekurzív módszerrel történő végrehajtásához az algoritmusunknak tartalmaznia kell egy alapesetet és egy rekurzív esetet, és a rekurzív eset továbbhalad az alapesetbe. Ellenkező esetben a folyamat soha nem fejeződik be, és egy végtelen hurkot eredményez.

A bináris keresési technika csökkenti azt az időt, amely alatt egy adott elemet megtalálunk egy rendezett tömbön belül. A bináris keresési módszert gyakran iteratív módon valósítják meg, de megvalósíthatjuk rekurzív módon is, ha kisebb darabokra bontjuk.

Kód

 #defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!') 

Kimenet:

 The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list 

A rekurzió rendkívül hatékony programozási és problémamegoldó technika. Használhatjuk különféle algoritmusok kiértékelésére és végrehajtására, az egyszerű iteratív problémáktól a bonyolult visszakövetési problémákig. Ebben az oktatóanyagban megvizsgáltuk a Python nyelv használatát a rekurzív bináris keresési módszer létrehozásához.