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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import random
def generate_test_data(length: int, _range: tuple):
arr = []
for i in range(length):
arr.append(random.randint(_range[0], _range[1]))
return arr
def binsearch(arr: list, item):
arr = sorted(arr)
print(arr)
ubound, lbound = len(arr) - 1, 0
found = False
while not found and lbound <= ubound:
index = (lbound + ubound) // 2
if lbound == ubound:
if arr[index] == item:
found = True
print("Found here")
if arr[index] > item:
ubound = index - 1
if arr[index] < item:
lbound = index + 1
def linear_search_while(arr: list, item):
found: bool = False
index = 0
while not found and index < len(arr):
if (arr[index] == item):
found = True
break
index += 1
return (found, index)
def linear_search(arr: list, item):
index = 0
for _item in arr:
if _item == item:
return (True, index)
index += 1
return False
def test_existsness(samples: int):
yes = 0
no = 0
for i in range(samples):
query = random.randint(0, 100)
array = generate_test_data(100, (0, 100))
found = linear_search(array, query)
if found:
yes += 1
else:
no += 1
print(f"In {samples} samples, {yes} match, {no} don't")
def main():
print("Hello world")
array = generate_test_data(10, (0, 100))
print(array)
query = int(input("Your query for item: "))
binsearch(array, query)
found1 = linear_search(array, query)
found2 = linear_search_while(array, query)
if found1[0]:
print("Found by for loop method ", found1[1])
else: print("Not found.")
if found2[0]:
print("Found by while loop method ", found2[1])
else:
print("Not found.")
test_existsness(100)
if __name__ == "__main__":
main()
|
