Find the smallest element in a sorted and rotated array I was solving a question asked in interview by Uber. It says:


  Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in \$O(\log n)\$ time. You may assume the array does not contain duplicates.


#include &lt;iostream&gt;

int find_smallest(int a[], int l, int r){
    if (l ==r)
        return a[l];
    else if (l+1 == r)
        return ((a[l] &lt; a[r]) ? a[l] : a[r]);
    else {
        int m = (l + r) / 2;
        int d1 = find_smallest(a, l, m);
        int d2 = find_smallest(a, m+1, r);
        return  ((d1 &lt; d2) ? d1 : d2);
    }
}


int main(){
    int a[] = {5,3,2,5,6,7};
    std::cout &lt;&lt; find_smallest(a, 0, 5);
}


Please ignore the hardcoding of values. It was just for testing.
Also, is the runtime of the code \$O(\log n)\$?
The input, 1) which doesn't contain duplicates, has been 2) sorted, 3) rotated:

int a[] = {5,3,2,5,6,7};
// removing duplicates gives
int a[] = {5,3,2,6,7};
// sorting gives
int a[] = {2,3,5,6,7};
// rotating gives (for instance):
int a[] = {5,6,7,2,3};


log(n) suggests a divide-and-conquer strategy like binary-search, as you found out by yourself. But what are you looking for in this case? Not a value, but the position where a[n] &gt; a[n+1]. Notice that if a[n] &gt; a[n+1], then also a[0] &gt; a[n+1]: the "direction change" occurred in that range. If not, it occurred in the range [a[n+1], a[len(a)]).

Divide-and-conquer is trickier than it may seem because it's really easy to access the array out-of-bounds. Iterator interfaces likes those of the C++ standard library make it easier and clearer:

template &lt;typename Iterator&gt;
Iterator find_partition_point(Iterator first, Iterator last) {
    if (first == last) return last; // empty array
    if (std::next(first) == last) return first; // one-value array
    if (*first &lt; *std::prev(last)) return first; // null/full rotation
    // so we have at least two elements and a change of direction
    auto pivot = first + std::distance(first, last) / 2;
    if (*pivot &lt; *first) { // direction change in [first, pivot]
        if (*std::prev(pivot) &gt; *pivot) return pivot;
        return find_partition_point(first, pivot);
    }
    return find_partition_point(std::next(pivot), last); // direction change in (pivot, last)
}