A Binary Search Example which has O(log n) time complexity.
(arr: List[int], lb: int, ub: int, target: int)
| 5 | |
| 6 | |
| 7 | def binary_search(arr: List[int], lb: int, ub: int, target: int) -> Optional[int]: |
| 8 | """ |
| 9 | A Binary Search Example which has O(log n) time complexity. |
| 10 | """ |
| 11 | while lb <= ub: |
| 12 | mid = lb + (ub - lb) // 2 |
| 13 | if arr[mid] == target: |
| 14 | return mid |
| 15 | elif arr[mid] < target: |
| 16 | lb = mid + 1 |
| 17 | else: |
| 18 | ub = mid - 1 |
| 19 | return -1 |
| 20 | |
| 21 | |
| 22 | def generate_random_list(size: int = 10, lower: int = 1, upper: int = 50) -> List[int]: |
no outgoing calls
no test coverage detected