Vi delar upp en samling objekt i två halvor i binär sökning för att minska antalet direkta jämförelser som behövs för att upptäcka ett element. Det finns dock ett krav: arrayens objekt måste sorteras i förväg.

Binär sökning

De Binär sökning Metoden lokaliserar indexet för en viss listmedlem. Det är bland de mest populära och snabbaste algoritmerna. För att den binära sökningen ska fungera bör posterna i listan sorteras.

Binär sökning är en effektivare sökteknik för att lokalisera ett elements index än Linjär sökning eftersom vi inte behöver granska varje listindex.

Den binära sökalgoritmens hela operation kan sammanfattas i följande steg:

• Leta reda på mittelementet i den sorterade arrayen.
• Gör en jämförelse mellan elementet som ska lokaliseras och mittelementet.
• Om det elementet är lika med mittelementet i den givna listan, returneras indexet för mittelementet. Annars kommer algoritmen att jämföra elementet med objektet i mitten.
• Nu, om elementet som ska lokaliseras är större än mitten av listan, kommer det att jämföras med den högra halvan av listan, d.v.s. element efter mittindexet.
• Eller om elementet är mindre än elementet i mitten av listan, kommer det att jämföras med endast den vänstra halvan av listan, dvs. element före mittindex.

Rekursiv binär sökning

Binär sökning innebär att kontinuerligt dela upp sökintervallet i 2 lika delar för att upptäcka ett element i en sorterad array, och återkommande binär sökning innebär att dela upp hela den binära sökproceduren i mindre frågor. En rekursiv binär sökning är rekursionssvaret på en binär sökning.

Följande är de egenskaper som helt rekursiva lösningar måste uppfylla:

1. Ett basfall krävs för ett rekursivt tillvägagångssätt.
2. Det måste finnas ett rekursivt testfall i ett rekursivt tillvägagångssätt.
3. Ett rekursivt tillvägagångssätt måste komma närmare basfallet.

Den lägsta underavdelningen av ett komplicerat problem representeras av ett basfall, vilket är ett slutfall. Så för att utföra den binära sökningen med rekursiv metod måste vår algoritm innehålla ett basfall och ett rekursivt fall, varvid det rekursiva fallet fortsätter till basfallet. Annars skulle processen aldrig avslutas och resultera i en oändlig loop.

Den binära söktekniken minskar tiden det tar att hitta ett specifikt element i en sorterad array. Den binära sökmetoden implementeras ofta iterativt, men vi kan också implementera den rekursivt genom att dela upp den i mindre bitar.

Koda

string.format java sträng

 #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!') 

Produktion:

 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 

Rekursion är en extremt kraftfull programmerings- och problemlösningsteknik. Vi kan använda den för att utvärdera och exekvera en mängd olika algoritmer, allt från enkla iterativa problem till komplicerade bakåtspårningsproblem. I den här handledningen tittade vi på att använda Python-språket för att skapa den rekursiva binära sökmetoden.