- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_search.py
More file actions
Latest commit
103 lines (88 loc) · 3.61 KB
/
Copy pathbinary_search.py
File metadata and controls
103 lines (88 loc) · 3.61 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#!/usr/bin/env python3
"""
Binary search, also known as logarithmic search, is a search algorithm that finds the
position of a target value within a sorted array.
"""
# ==================== Binary Search ====================
"""
Find the index of value in array using a binary search.
If the index can not be found, return None.
"""
defbinary_search(array, value):
ifarray==None: returnNone
array.sort()
returnbinary_search_recursive(array, value, 0, len(array) -1)
"""
Perform a binary search recursively between the given indices until the
value is found at an index or there are no more elements to search.
The array argument must be sorted.
"""
defbinary_search_recursive(array, value, lower_index, upper_index):
# Check if the bounding indices have a middle index.
# If not, return None
iflower_index>upper_index: returnNone
# Get the index in the middle of the lower and upper indices.
# Use the floor function to take the lower of the middle indices
# when there is 2.
index= (lower_index+upper_index) //2
# Update the search indices based on the value of this middle index
ifarray[index] ==value:
# Success, return the index
returnindex
elifarray[index] >value:
# The value at this index is too large.
# Search to the left from [lowerIndex, index - 1]
returnbinary_search_recursive(array, value, lower_index, index-1)
else:
# The value at this index is too small.
# Search to the right from [index + 1, upperIndex]
returnbinary_search_recursive(array, value, index+1, upper_index)
# ==================== Test ====================
deftest_binary_search(array, value, expected_index):
index=binary_search(array, value)
ifindex==expected_index:
print("Success")
else:
print(f"Failure, returned {index} but expected {expected_index}")
deftest_all():
# Integers, None, empty, or one
test_binary_search(None, None, None)
test_binary_search(None, 0, None)
test_binary_search([], 0, None)
test_binary_search([1], 0, None)
test_binary_search([100], 100, 0)
# Integers, basic
test_binary_search([1, 2, 3], 0, None)
test_binary_search([1, 2, 3], 1, 0)
test_binary_search([1, 2, 3], 2, 1)
test_binary_search([1, 2, 3], 3, 2)
test_binary_search([1, 2, 3], 4, None)
# Strings, basic
test_binary_search(["a", "b", "c"], "", None)
test_binary_search(["a", "b", "c"], "a", 0)
test_binary_search(["a", "b", "c"], "b", 1)
test_binary_search(["a", "b", "c"], "c", 2)
test_binary_search(["a", "b", "c"], "d", None)
# Integers, basic, unsorted
test_binary_search([3, 1, 2], 1, 0)
test_binary_search([3, 1, 2], 2, 1)
test_binary_search([3, 1, 2], 3, 2)
# Integers
test_binary_search([1, 5, 9, 12, 17], 1, 0)
test_binary_search([1, 5, 9, 12, 17], 5, 1)
test_binary_search([1, 5, 9, 12, 17], 9, 2)
test_binary_search([1, 5, 9, 12, 17], 12, 3)
test_binary_search([1, 5, 9, 12, 17], 17, 4)
test_binary_search([1, 5, 9, 12, 17], 0, None)
test_binary_search([1, 5, 9, 12, 17], 2, None)
test_binary_search([1, 5, 9, 12, 17], 4, None)
test_binary_search([1, 5, 9, 12, 17], 6, None)
test_binary_search([1, 5, 9, 12, 17], 8, None)
test_binary_search([1, 5, 9, 12, 17], 10, None)
test_binary_search([1, 5, 9, 12, 17], 11, None)
test_binary_search([1, 5, 9, 12, 17], 13, None)
test_binary_search([1, 5, 9, 12, 17], 16, None)
test_binary_search([1, 5, 9, 12, 17], 18, None)
# ==================== Main ====================
if__name__=="__main__":
test_all()