Kursy Online

Lekcja – wyszukiwanie przez interpolację (interpolate search)

def search_interpolate(value, list):     
    
    start = 0     
    end = len(list) - 1
    found = False

    while start <= end and value >= list[start] and value <= list[end]:
        print(f'DEBUG: {start} - {end}')
 
        # Find the mid point
        if list[start] != list[end]:         
            mid = start + int(  ( float(end - start) / (list[end] - list[start]) ) 
                                * (value - list[start]) )
        else:
            mid = start
        print(f'DEBUG: proposed mid = {mid}')

        # Compare the value at mid point with search value 
        if list[mid] == value: 
            print(f"DEBUG: found on position {mid}!!!")
            found = True
            break             
        else:
            if value < list[mid]:             
                end = mid - 1 
                print(f'DEBUG: changing end to {end}')
            else:
                start = mid + 1    
                print(f'DEBUG: changing start to {start}')
    
    if found:
        return mid
    else:
        return None


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


list = [0, 1, 2, 3, 3, 4, 5, 6, 700, 900]
search_value = 6
idx = search_interpolate(search_value, list)
print(f'{search_value} is on the {list} on position {idx}')

Rozwiązanie

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



def search_interpolate(value, list):     
    
    start = 0     
    end = len(list) - 1
    found = False

    while start <= end and value >= list[start] and value <= list[end]:
        # print(f'DEBUG: {start} - {end}')
 
        # Find the mid point
        if list[start] != list[end]:         
            mid = start + int(  ( float(end - start) / (list[end] - list[start]) ) 
                                * (value - list[start]) )
        else:
            mid = start
        # print(f'DEBUG: proposed mid = {mid}')

        # Compare the value at mid point with search value 
        if list[mid] == value: 
            # print(f"DEBUG: found on position {mid}!!!")
            found = True
            break             
        else:
            if value < list[mid]:             
                end = mid - 1 
                # print(f'DEBUG: changing end to {end}')
            else:
                start = mid + 1    
                # print(f'DEBUG: changing start to {start}')
    
    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 - binary search

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


# checking time - interpolate search

start = time.perf_counter_ns()
idx = search_interpolate(value, ordered_list)
stop = time.perf_counter_ns()
print(f'Interpolation search: value found at {idx} in {stop - start} nano seconds')