deneme_sahasi/python/binary_search.py at main · mal1kc/deneme_sahasi · GitHub

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
70
71
import time
from random import randint
def binary_search(numbers: list, target: int) -> int | None:
    lower = 0
    higher = len(numbers)
    while lower <= higher:
        mid = (lower + higher) // 2
        if mid >= len(numbers):
            break
        if numbers[mid] == target:
            return mid
        if target < numbers[mid]:
            higher = mid - 1
        else:
            lower = mid + 1
    return None


def main() -> None:
    # test cases
    numbers = list(range(1, 101))
    print(" start testing with numbers from 1 to 100")
    assert binary_search(numbers, 1) == 0
    assert binary_search(numbers, 100) == 99
    assert binary_search(numbers, 50) == 49
    assert binary_search(numbers, 101) is None
    assert binary_search(numbers, 0) is None
    print(" test passed")


    bigger_numbers = list(range(1, 1001))
    print(" start testing with numbers from 1 to 1000")
    assert binary_search(bigger_numbers, 1) == 0
    assert binary_search(bigger_numbers, 1000) == 999
    assert binary_search(bigger_numbers, 500) == 499
    assert binary_search(bigger_numbers, 1001) is None
    assert binary_search(bigger_numbers, 0) is None
    print(" test passed")

    random_sorted_numbers = sorted([randint(x, 10001) for x in range(1000)])
    print(" start testing with random sorted numbers")
    assert binary_search(random_sorted_numbers, random_sorted_numbers[0]) == 0
    assert (
        binary_search(random_sorted_numbers, random_sorted_numbers[-1])
        == len(random_sorted_numbers) - 1
    )
    assert binary_search(random_sorted_numbers,  random_sorted_numbers[500]) == 500
    print(" test passed")

    # i want to be sure it works without failing
    # very_very_long_list = list(range(1, 1_000_000_001))
    # print(" start testing with numbers from 1 to 1_000_000_000")
    # assert binary_search(very_very_long_list, 1) == 0
    # assert binary_search(very_very_long_list, 1_000_000_000) == 999_999_999
    # assert binary_search(very_very_long_list, 500_000_000) == 499_999_999
    # assert binary_search(very_very_long_list, 1_000_000_001) is None
    # assert binary_search(very_very_long_list, 0) is None
    # print(" test passed")


if __name__ == "__main__":
    try:
        start = time.time()
        main()
        print("tests completed  in " + str(time.time() - start) + " seconds")
        exit(0)
    except AssertionError:
        print("Test failed")
        exit(1)