|
| 1 | +""" |
| 2 | +Pure Python implementation of a binary search algorithm. |
| 3 | +
|
| 4 | +For doctests run following command: |
| 5 | +python3 -m doctest -v simple_binary_search.py |
| 6 | +
|
| 7 | +For manual testing run: |
| 8 | +python3 simple_binary_search.py |
| 9 | +""" |
| 10 | +from typing import List |
| 11 | + |
| 12 | + |
| 13 | +def binary_search(a_list: List[int], item: int) -> bool: |
| 14 | + """ |
| 15 | + >>> test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42] |
| 16 | + >>> print(binary_search(test_list, 3)) |
| 17 | + False |
| 18 | + >>> print(binary_search(test_list, 13)) |
| 19 | + True |
| 20 | + >>> print(binary_search([4, 4, 5, 6, 7], 4)) |
| 21 | + True |
| 22 | + >>> print(binary_search([4, 4, 5, 6, 7], -10)) |
| 23 | + False |
| 24 | + >>> print(binary_search([-18, 2], -18)) |
| 25 | + True |
| 26 | + >>> print(binary_search([5], 5)) |
| 27 | + True |
| 28 | + >>> print(binary_search(['a', 'c', 'd'], 'c')) |
| 29 | + True |
| 30 | + >>> print(binary_search(['a', 'c', 'd'], 'f')) |
| 31 | + False |
| 32 | + >>> print(binary_search([], 1)) |
| 33 | + False |
| 34 | + >>> print(binary_search([.1, .4 , -.1], .1)) |
| 35 | + True |
| 36 | + """ |
| 37 | + if len(a_list) == 0: |
| 38 | + return False |
| 39 | + midpoint = len(a_list) // 2 |
| 40 | + if a_list[midpoint] == item: |
| 41 | + return True |
| 42 | + if item < a_list[midpoint]: |
| 43 | + return binary_search(a_list[:midpoint], item) |
| 44 | + else: |
| 45 | + return binary_search(a_list[midpoint + 1:], item) |
| 46 | + |
| 47 | + |
| 48 | +if __name__ == "__main__": |
| 49 | + user_input = input("Enter numbers separated by comma:\n").strip() |
| 50 | + sequence = [int(item.strip()) for item in user_input.split(",")] |
| 51 | + target = int(input("Enter the number to be found in the list:\n").strip()) |
| 52 | + not_str = "" if binary_search(sequence, target) else "not " |
| 53 | + print(f"{target} was {not_str}found in {sequence}") |
0 commit comments