Find Min in Rotated Array

Question

I am trying to find the minimum element in a sorted array which has been rotated.

Example:

     1 2 3 4 5 => sorted

     3 4 5 1 2 => Rotated => Find the min in this in O(log n)

I have tried to write the code :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int bs(vector<int> a)
{
    int l =0, r = a.size()-1;

    while(l<=r)
    {
        int mid = l + (r-l)/2; // Mid guaranteed to be in range

        if(a[mid-1]>a[mid]) return a[mid];

        if(a[mid]>a[l])
        {
            l=mid+1 ; continue;
        }
        else
        {
            r = mid-1 ; //Mid has been checked
        }
    }
}

int main()
{
  vector<int> a = {1,2,3,5,6,7,8,9,10};
  rotate(a.begin(),a.begin()+4,a.end()); //  Make 6 the head 
  for(auto x:a) cout<<x<<endl;
  cout <<"Min is " <<bs(a) <<endl;
  return 0;
}

I get the output:

, which is clearly wrong. I guess I am manipulating the binary search conditions to adapt to my problem, but I can't figure out what is wrong.

My method is similar to this, and I think I am doing logically correct, which is of course wrong thinking.

Why don't you add some printouts to tell you what your code is doing? — Ami Tavory, Jul 11 '15 at 15:48
[running your code](https://ideone.com/NSWNEG) yields "Min is 3" — m.s., Jul 11 '15 at 15:50
Once you rotate the vector, it's no longer sorted and you can't use binary search. — Some programmer dude, Jul 11 '15 at 15:54
WHy people are downvoting and nobody is answering ? If the question is dead simple, please take a few seconds to answer, downvoting does not help at all. THis is my second question at SO only. — Martin Lampard, Jul 11 '15 at 15:55
@JoachimPileborg No sir you got it totally wrong. I am not using Bin search, this is the algo to find min, it is not binary search. — Martin Lampard, Jul 11 '15 at 15:55
The solution *is* dead simple, use [`std::min_element`](http://en.cppreference.com/w/cpp/algorithm/min_element). — Some programmer dude, Jul 11 '15 at 15:56
@JoachimPileborg Is it O(log n) ? No, it needs Exactly max(N-1,0) comparisons, where N = std::distance(first, last). So, it is O(n). My code intends to solve in O(log n). — Martin Lampard, Jul 11 '15 at 15:56
Your method *looks* very much like a binary search... You divide the range in two parts, check two value and adjust the divider position, just like a binary search. The problem is that since your vector is no longer sorted, you *can't* just split down the middle. — Some programmer dude, Jul 11 '15 at 15:58
@JoachimPileborg Yes it is derived from binary search by modifying some checks, that's all, it's an application of binary search. — Martin Lampard, Jul 11 '15 at 15:58
I suggest you step through the code, line by line, in a debugger. — Some programmer dude, Jul 11 '15 at 15:59
I really don't understand what you're asking. It is a sorted rotated array. Do you know the rotation? If so, you know the index of the min element. If not, why do you think it can be solved in log time? — Ami Tavory, Jul 11 '15 at 15:59
@JoachimPileborg No, if you go to the link in my question, you would realise what I am saying. But thanks, you helped , others just downvoted. THanks. — Martin Lampard, Jul 11 '15 at 16:00
@AmiTavory plz see there is a solution in Java that I have referred in the link. It is a algorithm problem. — Martin Lampard, Jul 11 '15 at 16:01
Downvotes Only, guess I should leave SO, everybody is too intelligent here to find my question disgusting. — Martin Lampard, Jul 11 '15 at 16:05
[This may be helpful](http://stackoverflow.com/questions/4773807/searching-in-an-sorted-and-rotated-array). The goal is different, but the logic is the same. You now have 2 sorted arrays split on the pivot point. All you have to do is find the pivot, then you can pick the first value on each side of the pivot and return the lowest. — user4581301, Jul 11 '15 at 16:18

Gene · Accepted Answer · 2015-07-12T02:36:51.313

You have the right strategy, but have not thought clearly about invariants.

I will assume the elements are distinct. Without this, it can't be done in O(log n) time. (Consider the case where all elements are 0 except a single 1.)

If a[0] < a[size-1], then there was no effective rotation, so a[0] is the min.

Otherwise there are two increasing runs a[0]<a[1]<...<a[k-1] and a[k]<a[k+1]<...<a[size-1], where we also know a[k-1]>a[k].

We want to find k.

Start - as you did - with a bracket [0, size-1] of guesses.

The invariant is that this bracket must always contain k. Certainly this is true for the initial bracket!

To ensure termination, we must make it smaller during each iteration. When the interval has only one element, i.e. lo == hi, we have the answer.

Computing a new guess is as you showed,

int mid = (lo + hi) / 2;

Now, what are the possibilities? Mid lies either in [0, k-1] or [k, size-1].

If the former, then we know mid <= k-1. We can make the bracket [mid+1, hi] while maintaining the invariant. Note that this always makes the bracket smaller, ensuring termination.

If it's the latter, we know mid >= k, so can use [lo, mid]. Note we can't say [lo, mid-1] because mid might be equal to k, breaking the invariant.

This raises another concern. If the calculation of mid were to produce mid == hi, then the new bracket is the same as the old. We'd have no progress and an infinite loop. Happily this never happens because (lo + hi) / 2 < hi whenever lo < hi.

The last piece of the puzzle is how to tell which run mid lies in. This is easy. If a[mid] >= a[0], we know it lies in the first run. Else it lies in the second.

Wrapping all this up in code:

if (a[0] < a[size - 1]) return 0;
int lo = 0, hi = size - 1;
while (lo < hi) {
  int mid = (lo + hi) / 2;
  if (a[mid] >= a[0])
    lo = mid + 1;
  else
    hi = mid;
}
return lo;

Could you once have a look at http://stackoverflow.com/questions/31356239/significance-of-equal-to-in-binary-search . Another question related to binary search. Thanks a lot :)) — Martin Lampard, Jul 11 '15 at 17:40
@MartinLampard You can answer this question with exactly the same technique I just used. I won't deprive you of this pleasure. Establish the invariant. Find a terminating condition that when "anded" with the invariant implies the answer. Make sure there is progress on each iteration. This will work without fail. NB: There are correct versions of binary search that rely on slightly different invariants. Therefore they can use different terminating conditions to imply the answer has been reached. Of slightly different terminating conditions can imply the answer for the same invariant. — Gene, Jul 11 '15 at 17:58

Shreevardhan · Answer 2 · 2015-07-11T17:05:28.133

Simply find the point of rotation using

auto sorted_end = is_sorted_until(a.begin(), a.end());

Description from cppreference:

Examines the range [first, last) and finds the largest range beginning at first in which the elements are sorted in ascending order.

To get min in both ways of rotation, use

min(a.front(), *is_sorted_until(a.begin(), a.end()))

This is less than O(n) but not O(log n).

EDIT Since you linked the SO thread, I am translating the answer in C++

int findMin(vector<int> & arr) {
    int low = 0;
    int high = arr.size() - 1;
    while (arr[low] > arr[high]) {
        int mid = (low + high) >> 1;
        if (arr[mid] > arr[high])
            low = mid + 1;
        else
            high = mid;
    }
    return arr[low];
}

See it working at http://ideone.com/BlzrWj.

score 0 · Answer 3 · answered Jul 11 '15 at 17:07

This has the smell of an assignment, so no standard library.

My cut was to find the pivot point by looking for the discontinuity:

int findpivot(vector<int> a)
{
    int left = 0;
    int right = a.size() - 1;

    while (a[left] > a[right])
    {
        int mid = (right + left) / 2;
        if (a[mid] > a[right])
        { 
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return left;
}

I would then look at the first value on both sides of the pivot for the lowerst. Running the function found (and in hindsight, "Duh!") that it always returned the index of the lowest value because of the way I looked for the discontinuity at the pivot.

The end result is identical to the Java solution with the exception that I return the pivot point and the Java solution returned the value at the pivot point.

As for the second question, why is the OP being downvoted? The OP is not being downvoted. The OP's question is.

OK, so why is the OP's question being downvoted?

The best answer I can come up with is this question is a duplicate. OP found the duplicate and didn't implement it correctly. That limits the usefulness of this question to future askers.

THanks but I am supposed to use l and r in the while check condition, not a[l] and a[r]. — Martin Lampard, Jul 11 '15 at 17:30
No, it is not duplicate, I am using a slightly different algorithm with l and r, I wrote similar algorithm, not duplicate. — Martin Lampard, Jul 11 '15 at 17:31
@MartinLampard First comment. Either has the same result with the same time complexity, though directly using left and right likely has a faster runtime. Comment 2: You were using a different algorithm, but the different algorithm didn't work. Making it work resulted in an optimized version of the java solution and pushes the question back to being a duplicate. On the up side, Gene provided an optimized version that future askers can use. +1, Gene. — user4581301, Jul 11 '15 at 19:21

score 0 · Answer 4 · answered Jul 11 '15 at 17:16

Try this one:

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
int findMinInRotatedSortedVec(vector<int>v, int start, int end)
{
    if (start == end) return v[start];
    int mid = (end-start)/2+start;
    if (v[start] == v[mid]) {
        if (v[mid] == v[end]) {
            int min1 = findMinInRotatedSortedVec(v, start, mid);
            int min2 = findMinInRotatedSortedVec(v, mid+1, end);
            return (min1 > min2) ? min2 : min1;
        }
        if (v[mid] < v[end]) return v[start];
    }
    if ((v[start] < v[mid]) && (v[mid] <= v[end])) return v[start];
    if (v[start] > v[mid]) return findMinInRotatedSortedVec(v, start, mid);
    return findMinInRotatedSortedVec(v, mid+1, end);
}

int main() {
    vector<int> v (70);
    std::iota(v.begin(), v.end(), 31);
    rotate(v.begin(),v.begin()+43,v.end());
    cout <<"Min is " << findMinInRotatedSortedVec(v,0,v.size()-1) <<endl;
  return 0;
}

score -1 · Answer 5 · edited Jul 11 '15 at 16:06

-1

<algorithm> provides a built-in method for finding the minimum element called min_element (in addition to max and minmax).

You can use it like this:

std::vector<int>::iterator result = std::min_element(std::begin(a), std::end(a));
std::cout << "Min is " << std::distance(std::begin(a), result);

and not have to use your bs() method at all.

edited Jul 11 '15 at 16:06

Thomas Ayoub

29,063
15
95
142

answered Jul 11 '15 at 16:05

aJetHorn

138
1
8

No, I can't take it for answer. – Martin Lampard Jul 11 '15 at 16:06
1

This solution is O(n), which is an overkill. – amit Jul 11 '15 at 16:21

Find Min in Rotated Array

5 Answers5