Using Binary Search find the number closest to target in the given sorted array
(arr, n, t)
| 6 | |
| 7 | |
| 8 | def find_closest(arr, n, t): |
| 9 | """ |
| 10 | Using Binary Search find the number closest |
| 11 | to target in the given sorted array |
| 12 | """ |
| 13 | if t <= arr[0]: |
| 14 | return arr[0] |
| 15 | elif t >= arr[n - 1]: |
| 16 | return arr[n - 1] |
| 17 | left, right = 0, n |
| 18 | while left < right: |
| 19 | mid = (left + right) // 2 |
| 20 | if arr[mid] == t: |
| 21 | return arr[mid] |
| 22 | elif t < arr[mid]: |
| 23 | if mid > 0 and arr[mid - 1] < t: |
| 24 | return get_closest(arr[mid - 1], arr[mid], t) |
| 25 | right = mid |
| 26 | else: |
| 27 | if mid < n - 1 and arr[mid + 1] > t: |
| 28 | return get_closest(arr[mid], arr[mid + 1], t) |
| 29 | left = mid + 1 |
| 30 | return arr[mid] |
| 31 | |
| 32 | |
| 33 | if __name__ == "__main__": |
no test coverage detected