Monday, April 16, 2018

find min in rotated array

se
m
12
21

sme
123
231
312
int findMinRotated(a, start = 0, end = a.length() -1):
    if start > end:
        throw
    if start == end:
        return a[start]
    if start +1 == end:
        return min(a[start], a[end])
    mid = start + (end-start)/2
    if a[start] < a[mid] < a[end]:
        return a[start]
    if a[start] < a[mid]:
        return findMinRotated(a, mid, end)
    if a[mid] < a[end]:
        return findMinRotated(a, start, mid)
    throw
[Hat tip to JR]

No comments:

Post a Comment