## Lekcja – wyszukiwanie binarne (binary search)

```def search_binary(value, list):

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

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

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

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

```