Pure implementation of binary search algorithm in Python Be careful collection must be sorted, otherwise result will be unpredictable :param sorted_collection: some sorted collection with comparable items :param item: item value to search :return: index of found item or None if
(sorted_collection, item)
| 19 | |
| 20 | |
| 21 | def binary_search(sorted_collection, item): |
| 22 | """Pure implementation of binary search algorithm in Python |
| 23 | |
| 24 | Be careful collection must be sorted, otherwise result will be |
| 25 | unpredictable |
| 26 | |
| 27 | :param sorted_collection: some sorted collection with comparable items |
| 28 | :param item: item value to search |
| 29 | :return: index of found item or None if item is not found |
| 30 | |
| 31 | Examples: |
| 32 | >>> binary_search([0, 5, 7, 10, 15], 0) |
| 33 | 0 |
| 34 | |
| 35 | >>> binary_search([0, 5, 7, 10, 15], 15) |
| 36 | 4 |
| 37 | |
| 38 | >>> binary_search([0, 5, 7, 10, 15], 5) |
| 39 | 1 |
| 40 | |
| 41 | >>> binary_search([0, 5, 7, 10, 15], 6) |
| 42 | |
| 43 | """ |
| 44 | left = 0 |
| 45 | right = len(sorted_collection) - 1 |
| 46 | |
| 47 | while left <= right: |
| 48 | midpoint = (left + right) // 2 |
| 49 | current_item = sorted_collection[midpoint] |
| 50 | if current_item == item: |
| 51 | return midpoint |
| 52 | else: |
| 53 | if item < current_item: |
| 54 | right = midpoint - 1 |
| 55 | else: |
| 56 | left = midpoint + 1 |
| 57 | return None |
| 58 | |
| 59 | |
| 60 | def binary_search_std_lib(sorted_collection, item): |