A pure Python implementation of a fibonacci search algorithm. Parameters ---------- arr List of sorted elements. val Element to search in list. Returns ------- int The index of the element in the array. -1 if the element is not found.
(arr: list, val: int)
| 56 | |
| 57 | |
| 58 | def fibonacci_search(arr: list, val: int) -> int: |
| 59 | """A pure Python implementation of a fibonacci search algorithm. |
| 60 | |
| 61 | Parameters |
| 62 | ---------- |
| 63 | arr |
| 64 | List of sorted elements. |
| 65 | val |
| 66 | Element to search in list. |
| 67 | |
| 68 | Returns |
| 69 | ------- |
| 70 | int |
| 71 | The index of the element in the array. |
| 72 | -1 if the element is not found. |
| 73 | |
| 74 | >>> fibonacci_search([4, 5, 6, 7], 4) |
| 75 | 0 |
| 76 | >>> fibonacci_search([4, 5, 6, 7], -10) |
| 77 | -1 |
| 78 | >>> fibonacci_search([-18, 2], -18) |
| 79 | 0 |
| 80 | >>> fibonacci_search([5], 5) |
| 81 | 0 |
| 82 | >>> fibonacci_search(['a', 'c', 'd'], 'c') |
| 83 | 1 |
| 84 | >>> fibonacci_search(['a', 'c', 'd'], 'f') |
| 85 | -1 |
| 86 | >>> fibonacci_search([], 1) |
| 87 | -1 |
| 88 | >>> fibonacci_search([.1, .4 , 7], .4) |
| 89 | 1 |
| 90 | >>> fibonacci_search([], 9) |
| 91 | -1 |
| 92 | >>> fibonacci_search(list(range(100)), 63) |
| 93 | 63 |
| 94 | >>> fibonacci_search(list(range(100)), 99) |
| 95 | 99 |
| 96 | >>> fibonacci_search(list(range(-100, 100, 3)), -97) |
| 97 | 1 |
| 98 | >>> fibonacci_search(list(range(-100, 100, 3)), 0) |
| 99 | -1 |
| 100 | >>> fibonacci_search(list(range(-100, 100, 5)), 0) |
| 101 | 20 |
| 102 | >>> fibonacci_search(list(range(-100, 100, 5)), 95) |
| 103 | 39 |
| 104 | """ |
| 105 | len_list = len(arr) |
| 106 | # Find m such that F_m >= n where F_i is the i_th fibonacci number. |
| 107 | i = 0 |
| 108 | while True: |
| 109 | if fibonacci(i) >= len_list: |
| 110 | fibb_k = i |
| 111 | break |
| 112 | i += 1 |
| 113 | offset = 0 |
| 114 | while fibb_k > 0: |
| 115 | index_k = min( |
nothing calls this directly
no test coverage detected