I ett nötskal drar den här sökalgoritmen fördel av en samling element som redan är sorterad genom att ignorera hälften av elementen efter bara en jämförelse.
- Jämför x med mittelementet.
- Om x matchar med mittelementet returnerar vi mittindexet.
- Annars om x är större än mittelementet, kan x bara ligga i den högra (större) halva subarrayen efter mittelementet. Sedan tillämpar vi algoritmen igen för den högra halvan.
- Annars om x är mindre måste målet x ligga i den vänstra (nedre) halvan. Så vi tillämpar algoritmen för den vänstra halvan.
Python-program för binär sökning med rekursiv
Python3
# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> ># Check base case> >if> high>>=> low:> >mid>=> (high>+> low)>/>/> 2> ># If element is present at the middle itself> >if> arr[mid]>=>=> x:> >return> mid> ># If element is smaller than mid, then it can only> ># be present in left subarray> >elif> arr[mid]>x:> >return> binary_search(arr, low, mid>-> 1>, x)> ># Else the element can only be present in right subarray> >else>:> >return> binary_search(arr, mid>+> 1>, high, x)> >else>:> ># Element is not present in the array> >return> ->1> # Test array> arr>=> [>2>,>3>,>4>,>10>,>40> ]> x>=> 10> # Function call> result>=> binary_search(arr,>0>,>len>(arr)>->1>, x)> if> result !>=> ->1>:> >print>(>'Element is present at index'>,>str>(result))> else>:> >print>(>'Element is not present in array'>)> |
>
sträng i c
>Produktion
Element is present at index 3>
Tidskomplexitet : O(log n)
Hjälputrymme : O(loggning) [OBS: Rekursion skapar samtalsstapel]
Python-program för binär sökning med iterativ
Python3
java slumptalsgenerator
# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> >low>=> 0> >high>=> len>(arr)>-> 1> >mid>=> 0> >while> low <>=> high:> >mid>=> (high>+> low)>/>/> 2> ># If x is greater, ignore left half> >if> arr[mid] low = mid + 1 # If x is smaller, ignore right half elif arr[mid]>x: hög = mitten - 1 # betyder att x är närvarande vid mitten annars: returnera mitten # Om vi når hit, då var elementet inte närvarande return -1 # Testarray arr = [ 2, 3, 4, 10, 40 ] x = 10 # Funktionsanropsresultat = binary_search(arr, x) if result != -1: print('Element finns i index', str(result)) else: print('Element finns inte i array' ')> |
>
>Produktion
Element is present at index 3>
Tidskomplexitet : O(log n)
Hjälputrymme : O(1)
Python-program för binär sökning Använder den inbyggda bisect-modulen
Steg för steg tillvägagångssätt:
string.substring java
- Koden importerar bisect-modulen som ger stöd för binär sökning.
- Funktionen binary_search_bisect() är definierad som tar en array arr och elementet för att söka x som indata.
- Funktionen anropar bisect_left()-funktionen för bisect-modulen som hittar positionen för elementet i den sorterade arrayen arr där x ska infogas för att behålla den sorterade ordningen. Om elementet redan finns i arrayen kommer denna funktion att återställa sin position.
- Funktionen kontrollerar sedan om det returnerade indexet i är inom intervallet för arrayen och om elementet vid det indexet är lika med x.
- Om villkoret är sant, returnerar funktionen index i som positionen för elementet i arrayen.
- Om villkoret är falskt returnerar funktionen -1 vilket indikerar att elementet inte finns i arrayen.
- Koden definierar sedan en array arr och ett element x att söka.
- Funktionen binary_search_bisect() anropas med arr och x som indata och det returnerade resultatet lagras i resultatvariabeln.
- Koden kontrollerar sedan om resultatet inte är lika med -1, vilket indikerar att elementet finns i arrayen. Om det är sant, skrivs elementets position i arrayen ut.
- Om resultatet är lika med -1, så skriver koden ut ett meddelande om att elementet inte finns i arrayen.
Python3
typscript switch
import> bisect> > def> binary_search_bisect(arr, x):> >i>=> bisect.bisect_left(arr, x)> >if> i !>=> len>(arr)>and> arr[i]>=>=> x:> >return> i> >else>:> >return> ->1> > > # Test array> arr>=> [>2>,>3>,>4>,>10>,>40>]> x>=> 10> > # Function call> result>=> binary_search_bisect(arr, x)> > if> result !>=> ->1>:> >print>(>'Element is present at index'>,>str>(result))> else>:> >print>(>'Element is not present in array'>)> |
>
>Produktion
Element is present at index 3>
Tidskomplexitet : O(log n)
Hjälputrymme : O(1)