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:
- A rekurzív megközelítéshez alapeset szükséges.
- A rekurzív megközelítésben rekurzív tesztesetnek kell lennie.
- 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.