-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathbinary_search.py
More file actions
61 lines (43 loc) · 1.38 KB
/
Copy pathbinary_search.py
File metadata and controls
61 lines (43 loc) · 1.38 KB
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
"""
Pure python implementation of binary search algorithm
For doc run following command.
python -m doctest -v binary_search.py
To run file use following command
python -m binary_search.py
"""
#imports
import bisect
def binary_search(sorted_collection, item):
"""
Prerequists: collections must be sorted in accending order
:param sorted_collection: any accending sorted collections
:param item: item to search
:return: index of item from sorted_collection or none if not found
Examples:
>>> binary_search([0, 1, 3, 5, 8, 9], 8)
4
>>> binary_search([0, 1, 3, 5, 8, 9], 3)
2
"""
left = 0
right = len(sorted_collection)-1
while left <= right:
midpoint = left + (right-left)//2
current_item = sorted_collection[midpoint]
if current_item == item:
return midpoint
else:
if item < current_item:
right = midpoint - 1
else:
left = midpoint + 1
return None
if __name__ == "__main__":
user_input = input("Enter the numbers seperated by commas: ")
collections = [int(i) for i in user_input.split(",")]
find_item = int(input("Enter the number to search: "))
result = binary_search(collections, find_item)
if result:
print(f'{find_item} found in {result}')
else:
print("The item you are looking is not found.")