diff options
Diffstat (limited to 'lesson1.py')
| -rw-r--r-- | lesson1.py | 34 |
1 files changed, 34 insertions, 0 deletions
@@ -4,6 +4,26 @@ def generate_test_data(length: int, _range: tuple): 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[lbound] == item: + found = True + print("Found here") + break + else: + break + 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 @@ -20,11 +40,24 @@ def linear_search(arr: list, 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]: @@ -34,5 +67,6 @@ def main(): print("Found by while loop method ", found2[1]) else: print("Not found.") + test_existsness(100) if __name__ == "__main__": main()
\ No newline at end of file |