c++ - Find Min in Rotated Array -

i trying find minimum element in sorted array has been rotated.

example:

     1 2 3 4 5 => sorted       3 4 5 1 2 => rotated => find min in in o(log n) 

i have tried write 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 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> = {1,2,3,5,6,7,8,9,10};   rotate(a.begin(),a.begin()+4,a.end()); //  make 6 head    for(auto x:a) cout<<x<<endl;   cout <<"min " <<bs(a) <<endl;   return 0; } 

i output:

6 7 8 9 10 1 2 3 5 min 3 

, wrong. guess manipulating binary search conditions adapt problem, can't figure out wrong.

my method similar this, , think doing logically correct, of course wrong thinking.

you have right strategy, have not thought invariants.

i assume elements distinct. without this, can't done in o(log n) time. (consider case elements 0 except single 1.)

if a[0] < a[size-1], there no effective rotation, a[0] min.

otherwise there 2 increasing runs a[0]<a[1]<...<a[k-1] , a[k]<a[k+1]<...<a[size-1], know a[k-1]>a[k].

we want find k.

start - did - bracket [0, size-1] of guesses.

the invariant bracket must contain k. true initial bracket!

to ensure termination, must make smaller during each iteration. when interval has 1 element, i.e. lo == hi, have answer.

computing new guess showed,

int mid = (lo + hi) / 2; 

now, possibilities? mid lies either in [0, k-1] or [k, size-1].

if former, know mid <= k-1. can make bracket [mid+1, hi] while maintaining invariant. note makes bracket smaller, ensuring termination.

if it's latter, know mid >= k, can use [lo, mid]. note can't [lo, mid-1] because mid might equal k, breaking invariant.

this raises concern. if calculation of mid produce mid == hi, new bracket same old. we'd have no progress , infinite loop. happily never happens because (lo + hi) / 2 < hi whenever lo < hi.

the last piece of puzzle how tell run mid lies in. easy. if a[mid] >= a[0], know lies in first run. else lies in second.

wrapping 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;