Interview challenge · medium · array, binary-search
Search in Rotated Sorted Array
El reto
El enunciado va en inglés, igual que en el vídeo.
A sorted array of distinct integers was rotated at an unknown pivot (for example [0, 1, 2, 4, 5, 6, 7] became [4, 5, 6, 7, 0, 1, 2]). Given a target, return its index, or -1 if it is not there. It must run in O(log n).
Example
[4, 5, 6, 7, 0, 1, 2], target 0 -> 4
[4, 5, 6, 7, 0, 1, 2], target 3 -> -1
[1], target 1 -> 0Idea: binary search, with one extra question at each step. When you cut a rotated array in half, at least one of the halves is sorted, and you can tell which by comparing its ends. If the target falls inside the sorted half, search there; otherwise search the other one. Time O(log n).
La solución
# Search in Rotated Array - ayotl.dev
def search(a, t):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == t:
return mid
# one half is always sorted
if a[lo] <= a[mid]:
if a[lo] <= t < a[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if a[mid] < t <= a[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
nums = [4, 5, 6, 7, 0, 1, 2]
print(search(nums, 0))
print(search(nums, 3))
print(search([1], 1))
$ python3 search_in_rotated_sorted_array.py
4
-1
0