## 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

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')