-
Notifications
You must be signed in to change notification settings - Fork 0
/
Searchcademy.py
28 lines (28 loc) · 870 Bytes
/
Searchcademy.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def sparse_search(data, search_val):
print("Data: " + str(data))
print("Search Value: " + str(search_val))
first, last = 0, len(data) - 1
while first <= last:
mid = (first + last) // 2
if not data[mid]:
left, right = mid - 1, mid + 1
while True:
if left < first and right > last:
print("{0} is not in the dataset".format(search_val))
return
elif right <= last and data[right]:
mid = right
break
elif left >= first and data[left]:
mid = left
break
right += 1
left -= 1
if data[mid] == search_val:
print("{0} found at position {1}".format(search_val, mid))
return
elif search_val < data[mid]:
last = mid - 1
elif search_val > data[mid]:
first = mid + 1
print("{0} is not in the dataset".format(search_val))