TheAlgorithms-Python

1
#!/usr/bin/env python3
2

3
"""
4
Pure Python implementations of binary search algorithms
5

6
For doctests run the following command:
7
python3 -m doctest -v binary_search.py
8

9
For manual testing run:
10
python3 binary_search.py
11
"""
12

13
from __future__ import annotations
14

15
import bisect
16

17

18
def bisect_left(
19
    sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
20
) -> int:
21
    """
22
    Locates the first element in a sorted array that is larger or equal to a given
23
    value.
24

25
    It has the same interface as
26
    https://docs.python.org/3/library/bisect.html#bisect.bisect_left .
27

28
    :param sorted_collection: some ascending sorted collection with comparable items
29
    :param item: item to bisect
30
    :param lo: lowest index to consider (as in sorted_collection[lo:hi])
31
    :param hi: past the highest index to consider (as in sorted_collection[lo:hi])
32
    :return: index i such that all values in sorted_collection[lo:i] are < item and all
33
        values in sorted_collection[i:hi] are >= item.
34

35
    Examples:
36
    >>> bisect_left([0, 5, 7, 10, 15], 0)
37
    0
38
    >>> bisect_left([0, 5, 7, 10, 15], 6)
39
    2
40
    >>> bisect_left([0, 5, 7, 10, 15], 20)
41
    5
42
    >>> bisect_left([0, 5, 7, 10, 15], 15, 1, 3)
43
    3
44
    >>> bisect_left([0, 5, 7, 10, 15], 6, 2)
45
    2
46
    """
47
    if hi < 0:
48
        hi = len(sorted_collection)
49

50
    while lo < hi:
51
        mid = lo + (hi - lo) // 2
52
        if sorted_collection[mid] < item:
53
            lo = mid + 1
54
        else:
55
            hi = mid
56

57
    return lo
58

59

60
def bisect_right(
61
    sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
62
) -> int:
63
    """
64
    Locates the first element in a sorted array that is larger than a given value.
65

66
    It has the same interface as
67
    https://docs.python.org/3/library/bisect.html#bisect.bisect_right .
68

69
    :param sorted_collection: some ascending sorted collection with comparable items
70
    :param item: item to bisect
71
    :param lo: lowest index to consider (as in sorted_collection[lo:hi])
72
    :param hi: past the highest index to consider (as in sorted_collection[lo:hi])
73
    :return: index i such that all values in sorted_collection[lo:i] are <= item and
74
        all values in sorted_collection[i:hi] are > item.
75

76
    Examples:
77
    >>> bisect_right([0, 5, 7, 10, 15], 0)
78
    1
79
    >>> bisect_right([0, 5, 7, 10, 15], 15)
80
    5
81
    >>> bisect_right([0, 5, 7, 10, 15], 6)
82
    2
83
    >>> bisect_right([0, 5, 7, 10, 15], 15, 1, 3)
84
    3
85
    >>> bisect_right([0, 5, 7, 10, 15], 6, 2)
86
    2
87
    """
88
    if hi < 0:
89
        hi = len(sorted_collection)
90

91
    while lo < hi:
92
        mid = lo + (hi - lo) // 2
93
        if sorted_collection[mid] <= item:
94
            lo = mid + 1
95
        else:
96
            hi = mid
97

98
    return lo
99

100

101
def insort_left(
102
    sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
103
) -> None:
104
    """
105
    Inserts a given value into a sorted array before other values with the same value.
106

107
    It has the same interface as
108
    https://docs.python.org/3/library/bisect.html#bisect.insort_left .
109

110
    :param sorted_collection: some ascending sorted collection with comparable items
111
    :param item: item to insert
112
    :param lo: lowest index to consider (as in sorted_collection[lo:hi])
113
    :param hi: past the highest index to consider (as in sorted_collection[lo:hi])
114

115
    Examples:
116
    >>> sorted_collection = [0, 5, 7, 10, 15]
117
    >>> insort_left(sorted_collection, 6)
118
    >>> sorted_collection
119
    [0, 5, 6, 7, 10, 15]
120
    >>> sorted_collection = [(0, 0), (5, 5), (7, 7), (10, 10), (15, 15)]
121
    >>> item = (5, 5)
122
    >>> insort_left(sorted_collection, item)
123
    >>> sorted_collection
124
    [(0, 0), (5, 5), (5, 5), (7, 7), (10, 10), (15, 15)]
125
    >>> item is sorted_collection[1]
126
    True
127
    >>> item is sorted_collection[2]
128
    False
129
    >>> sorted_collection = [0, 5, 7, 10, 15]
130
    >>> insort_left(sorted_collection, 20)
131
    >>> sorted_collection
132
    [0, 5, 7, 10, 15, 20]
133
    >>> sorted_collection = [0, 5, 7, 10, 15]
134
    >>> insort_left(sorted_collection, 15, 1, 3)
135
    >>> sorted_collection
136
    [0, 5, 7, 15, 10, 15]
137
    """
138
    sorted_collection.insert(bisect_left(sorted_collection, item, lo, hi), item)
139

140

141
def insort_right(
142
    sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1
143
) -> None:
144
    """
145
    Inserts a given value into a sorted array after other values with the same value.
146

147
    It has the same interface as
148
    https://docs.python.org/3/library/bisect.html#bisect.insort_right .
149

150
    :param sorted_collection: some ascending sorted collection with comparable items
151
    :param item: item to insert
152
    :param lo: lowest index to consider (as in sorted_collection[lo:hi])
153
    :param hi: past the highest index to consider (as in sorted_collection[lo:hi])
154

155
    Examples:
156
    >>> sorted_collection = [0, 5, 7, 10, 15]
157
    >>> insort_right(sorted_collection, 6)
158
    >>> sorted_collection
159
    [0, 5, 6, 7, 10, 15]
160
    >>> sorted_collection = [(0, 0), (5, 5), (7, 7), (10, 10), (15, 15)]
161
    >>> item = (5, 5)
162
    >>> insort_right(sorted_collection, item)
163
    >>> sorted_collection
164
    [(0, 0), (5, 5), (5, 5), (7, 7), (10, 10), (15, 15)]
165
    >>> item is sorted_collection[1]
166
    False
167
    >>> item is sorted_collection[2]
168
    True
169
    >>> sorted_collection = [0, 5, 7, 10, 15]
170
    >>> insort_right(sorted_collection, 20)
171
    >>> sorted_collection
172
    [0, 5, 7, 10, 15, 20]
173
    >>> sorted_collection = [0, 5, 7, 10, 15]
174
    >>> insort_right(sorted_collection, 15, 1, 3)
175
    >>> sorted_collection
176
    [0, 5, 7, 15, 10, 15]
177
    """
178
    sorted_collection.insert(bisect_right(sorted_collection, item, lo, hi), item)
179

180

181
def binary_search(sorted_collection: list[int], item: int) -> int:
182
    """Pure implementation of a binary search algorithm in Python
183

184
    Be careful collection must be ascending sorted otherwise, the result will be
185
    unpredictable
186

187
    :param sorted_collection: some ascending sorted collection with comparable items
188
    :param item: item value to search
189
    :return: index of the found item or -1 if the item is not found
190

191
    Examples:
192
    >>> binary_search([0, 5, 7, 10, 15], 0)
193
    0
194
    >>> binary_search([0, 5, 7, 10, 15], 15)
195
    4
196
    >>> binary_search([0, 5, 7, 10, 15], 5)
197
    1
198
    >>> binary_search([0, 5, 7, 10, 15], 6)
199
    -1
200
    """
201
    if list(sorted_collection) != sorted(sorted_collection):
202
        raise ValueError("sorted_collection must be sorted in ascending order")
203
    left = 0
204
    right = len(sorted_collection) - 1
205

206
    while left <= right:
207
        midpoint = left + (right - left) // 2
208
        current_item = sorted_collection[midpoint]
209
        if current_item == item:
210
            return midpoint
211
        elif item < current_item:
212
            right = midpoint - 1
213
        else:
214
            left = midpoint + 1
215
    return -1
216

217

218
def binary_search_std_lib(sorted_collection: list[int], item: int) -> int:
219
    """Pure implementation of a binary search algorithm in Python using stdlib
220

221
    Be careful collection must be ascending sorted otherwise, the result will be
222
    unpredictable
223

224
    :param sorted_collection: some ascending sorted collection with comparable items
225
    :param item: item value to search
226
    :return: index of the found item or -1 if the item is not found
227

228
    Examples:
229
    >>> binary_search_std_lib([0, 5, 7, 10, 15], 0)
230
    0
231
    >>> binary_search_std_lib([0, 5, 7, 10, 15], 15)
232
    4
233
    >>> binary_search_std_lib([0, 5, 7, 10, 15], 5)
234
    1
235
    >>> binary_search_std_lib([0, 5, 7, 10, 15], 6)
236
    -1
237
    """
238
    if list(sorted_collection) != sorted(sorted_collection):
239
        raise ValueError("sorted_collection must be sorted in ascending order")
240
    index = bisect.bisect_left(sorted_collection, item)
241
    if index != len(sorted_collection) and sorted_collection[index] == item:
242
        return index
243
    return -1
244

245

246
def binary_search_by_recursion(
247
    sorted_collection: list[int], item: int, left: int = 0, right: int = -1
248
) -> int:
249
    """Pure implementation of a binary search algorithm in Python by recursion
250

251
    Be careful collection must be ascending sorted otherwise, the result will be
252
    unpredictable
253
    First recursion should be started with left=0 and right=(len(sorted_collection)-1)
254

255
    :param sorted_collection: some ascending sorted collection with comparable items
256
    :param item: item value to search
257
    :return: index of the found item or -1 if the item is not found
258

259
    Examples:
260
    >>> binary_search_by_recursion([0, 5, 7, 10, 15], 0, 0, 4)
261
    0
262
    >>> binary_search_by_recursion([0, 5, 7, 10, 15], 15, 0, 4)
263
    4
264
    >>> binary_search_by_recursion([0, 5, 7, 10, 15], 5, 0, 4)
265
    1
266
    >>> binary_search_by_recursion([0, 5, 7, 10, 15], 6, 0, 4)
267
    -1
268
    """
269
    if right < 0:
270
        right = len(sorted_collection) - 1
271
    if list(sorted_collection) != sorted(sorted_collection):
272
        raise ValueError("sorted_collection must be sorted in ascending order")
273
    if right < left:
274
        return -1
275

276
    midpoint = left + (right - left) // 2
277

278
    if sorted_collection[midpoint] == item:
279
        return midpoint
280
    elif sorted_collection[midpoint] > item:
281
        return binary_search_by_recursion(sorted_collection, item, left, midpoint - 1)
282
    else:
283
        return binary_search_by_recursion(sorted_collection, item, midpoint + 1, right)
284

285

286
def exponential_search(sorted_collection: list[int], item: int) -> int:
287
    """Pure implementation of an exponential search algorithm in Python
288
    Resources used:
289
    https://en.wikipedia.org/wiki/Exponential_search
290

291
    Be careful collection must be ascending sorted otherwise, result will be
292
    unpredictable
293

294
    :param sorted_collection: some ascending sorted collection with comparable items
295
    :param item: item value to search
296
    :return: index of the found item or -1 if the item is not found
297

298
    the order of this algorithm is O(lg I) where I is index position of item if exist
299

300
    Examples:
301
    >>> exponential_search([0, 5, 7, 10, 15], 0)
302
    0
303
    >>> exponential_search([0, 5, 7, 10, 15], 15)
304
    4
305
    >>> exponential_search([0, 5, 7, 10, 15], 5)
306
    1
307
    >>> exponential_search([0, 5, 7, 10, 15], 6)
308
    -1
309
    """
310
    if list(sorted_collection) != sorted(sorted_collection):
311
        raise ValueError("sorted_collection must be sorted in ascending order")
312
    bound = 1
313
    while bound < len(sorted_collection) and sorted_collection[bound] < item:
314
        bound *= 2
315
    left = bound // 2
316
    right = min(bound, len(sorted_collection) - 1)
317
    last_result = binary_search_by_recursion(
318
        sorted_collection=sorted_collection, item=item, left=left, right=right
319
    )
320
    if last_result is None:
321
        return -1
322
    return last_result
323

324

325
searches = (  # Fastest to slowest...
326
    binary_search_std_lib,
327
    binary_search,
328
    exponential_search,
329
    binary_search_by_recursion,
330
)
331

332

333
if __name__ == "__main__":
334
    import doctest
335
    import timeit
336

337
    doctest.testmod()
338
    for search in searches:
339
        name = f"{search.__name__:>26}"
340
        print(f"{name}: {search([0, 5, 7, 10, 15], 10) = }")  # type: ignore[operator]
341

342
    print("\nBenchmarks...")
343
    setup = "collection = range(1000)"
344
    for search in searches:
345
        name = search.__name__
346
        print(
347
            f"{name:>26}:",
348
            timeit.timeit(
349
                f"{name}(collection, 500)", setup=setup, number=5_000, globals=globals()
350
            ),
351
        )
352

353
    user_input = input("\nEnter numbers separated by comma: ").strip()
354
    collection = sorted(int(item) for item in user_input.split(","))
355
    target = int(input("Enter a single number to be found in the list: "))
356
    result = binary_search(sorted_collection=collection, item=target)
357
    if result == -1:
358
        print(f"{target} was not found in {collection}.")
359
    else:
360
        print(f"{target} was found at position {result} of {collection}.")
361