Vi opdeler en samling af elementer i to halvdele i binær søgning for at reducere antallet af direkte sammenligninger, der er nødvendige for at opdage et element. Der er dog et krav: arrayets elementer skal sorteres på forhånd.

Binær søgning

Det Binær søgning Metode lokaliserer indekset for et bestemt listemedlem. Det er blandt de mest populære og hurtigste algoritmer. For at den binære søgningsprocedure skal fungere, skal posterne på listen sorteres.

Binær søgning er en mere effektiv søgeteknik til at lokalisere et elements indeks end Lineær søgning da vi ikke behøver at undersøge hvert listeindeks.

Den binære søgealgoritmes hele operation kan opsummeres i følgende trin:

• Find det midterste element i det sorterede array.
• Foretag en sammenligning mellem det element, der skal placeres, og det midterste element.
• Hvis dette element er lig med det midterste element i den givne liste, returneres indekset for det midterste element. Ellers vil algoritmen sammenligne elementet med elementet i midten.
• Nu, hvis elementet, der skal lokaliseres, er større end det midterste element på listen, vil det blive sammenlignet med den højre halvdel af listen, dvs. elementer efter det midterste indeks.
• Eller hvis elementet er mindre end elementet i midten af ​​listen, så vil det kun blive sammenlignet med den venstre halvdel af listen, dvs. elementer før det midterste indeks.

Rekursiv binær søgning

Binær søgning indebærer kontinuerlig opdeling af søgeintervallet i 2 lige store dele for at opdage et element i et sorteret array, og tilbagevendende binær søgning indebærer opdeling af den komplette binære søgeprocedure i mindre emner. En rekursiv binær søgning er rekursionssvaret på en binær søgning.

Følgende er de egenskaber, som alle rekursive løsninger skal opfylde:

1. Et basiscase er påkrævet for en rekursiv tilgang.
2. Der skal være en rekursiv testcase i en rekursiv tilgang.
3. En rekursiv tilgang skal komme tættere på basissagen.

Den laveste underinddeling af et kompliceret problem er repræsenteret af et basistilfælde, som er et endeligt tilfælde. Så for at udføre den binære søgning efter rekursiv metode skal vores algoritme indeholde et basistilfælde og et rekursivt tilfælde, hvor det rekursive tilfælde går videre til basistilfældet. Ellers ville processen aldrig slutte og resultere i en endeløs løkke.

Den binære søgeteknik reducerer den tid, det tager at finde et bestemt element inde i et sorteret array. Den binære søgemetode implementeres ofte iterativt, men vi kan også implementere den rekursivt ved at opdele den i mindre stykker.

Kode

 #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 er en ekstremt kraftfuld programmerings- og problemløsningsteknik. Vi kan bruge det til at evaluere og udføre en række forskellige algoritmer, lige fra simple iterative problemer til komplicerede tilbagesporingsproblemer. I denne tutorial så vi på at bruge Python-sproget til at skabe den rekursive binære søgemetode.