Binärsökning och linjär sökning i Python

Binärsökning är en algoritm med intervallhalvering som används för att hitta ett index för ett målvärde i en sorterad lista. Binärsökning är snabbare än linjär sökning (sekventiell sökning) om listan inte är väldigt liten. Binär sökning kräver att en lista är sorterad. Linjär sökning fungerar med en osorterad lista.

Linjär sökning körs i linjär tid O(n), algoritmen måste i värsta fall iterera över alla element i listan. Binärsökning körs i logaritmisk tid O(log n), i exemplet nedan behöver algoritmen bara fem steg i det värsta fallet (storleken på listan är 19 element). Linjär sökning innebär att vi itererar sökutrymmet i tur och ordning tills det att vi hittar målvärdet. Binärsökning innebär att vi alltid söker i mitten av sökutrymmet och att vi kan ignorera delar av sökutrymmet.

Exempel

Vi börjar med en osorterad lista som består av slumpmässigt genererade heltal och vill hitta ett målvärde på 12 i listan. Du kan sätta målvärdet till ett nummer som inte finns i listan för att utvärdera prestandan för det värsta fallet.

# Random integers in unsorted list
numbers = [1, 42, 7, 62, 59, 43, 10, 81, 62, 68, 58, 53, 46, 74, 12, 96, 66, 19, 31]

# Set the number to be found
target = 12

# Linear search
steps = 0
for i in range(len(numbers)):
    steps += 1
    if(numbers[i] == target):
        print('Linear search found target at index {0} in {1} step(s)'.format(i, steps))
        break

# Binary search (numbers must be sorted)
numbers.sort()
print('Sorted numbers: {0}'.format(numbers))
steps = 0
start = 0
end = len(numbers) - 1
while (start <= end):
    
    # Increase steps
    steps += 1

    # Calculate mid index
    mid = int((start + end) / 2)
          
    # Check if target is in middle
    if (numbers[mid] == target): 
        print('Binary search found target at index {0} in {1} step(s)'.format(mid, steps))
        break
    elif (numbers[mid] < target): 
        start = mid + 1 # Restrict search space to right half
    elif (numbers[mid] > target):
        end = mid - 1 # Restrict search space to left half

Utdata

Linear search found target at index 14 in 15 step(s)
Sorted numbers: [1, 7, 10, 12, 19, 31, 42, 43, 46, 53, 58, 59, 62, 62, 66, 68, 74, 81, 96]
Binary search found target at index 3 in 5 step(s)