Kursy Online

Lekcja – wyszukiwanie binarne (binary search)

def search_binary(value, list): 

    start = 0 
    end = len(list)-1 
    found = False 

    while start <= end and not found:         
        print(f'DEBUG {start} - {end}')
        mid = (start + end) // 2         
        if list[mid] == value:             
            found = True         
        else:             
            if value < list[mid]:                 
                end = mid - 1             
            else:                 
                start = mid + 1     
    
    if found:
        return mid
    else:
        return None


list = [0, 1, 2, 3, 3, 4, 5, 6, 7, 9]
value = 5.5
idx = search_binary(value, list)
print(f'{value} is on the {list} on position {idx}')

Rozwiązanie

def search_linear(value, list):

    idx = 0
    found = False

    while not found and idx < len(list):
        if list[idx] == value:
            found = True
        else:
            idx += 1

    return idx if idx < len(list) else None


def search_binary(value, list): 

    start = 0 
    end = len(list)-1 
    found = False 

    while start <= end and not found:         
        mid = (start + end) // 2 
        if list[mid] == value:             
            found = True         
        else:             
            if value < list[mid]:                 
                end = mid - 1             
            else:                 
                start = mid + 1     
    
    if found:
        return mid
    else:
        return None


import time
import random

max_len = 100000000
ordered_list = list(range(max_len))
value = random.randint(0, max_len)

print(f'Searching value {value}')

# checking time - linear search

start = time.perf_counter()
idx = search_linear(value, ordered_list)
stop = time.perf_counter()
print(f'Linear search: value found at {idx} in {stop - start} seconds')


# checking time - binary search

start = time.perf_counter()
idx = search_binary(value, ordered_list)
stop = time.perf_counter()
print(f'Binary search: value found at {idx} in {stop - start} seconds')