fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int bs(vector<int> a)
  8. {
  9.     int l =0, r = a.size()-1;
  10.  
  11.     while(l<=r)
  12.     {
  13.         int mid = l + (r-l)/2; // Mid guaranteed to be in range
  14.  
  15.         if(a[mid-1]>a[mid]) return a[mid];
  16.  
  17.         if(a[mid]>a[l])
  18.         {
  19.             l=mid+1 ; continue;
  20.         }
  21.         else
  22.         {
  23.             r = mid-1 ; //Mid has been checked
  24.         }
  25.     }
  26. }
  27.  
  28. int main()
  29. {
  30.   vector<int> a = {1,2,3,5,6,7,8,9,10};
  31.   rotate(a.begin(),a.begin()+4,a.end());
  32.   for(auto x:a) cout<<x<<endl;
  33.   cout <<"Min is " <<bs(a) <<endl;
  34.   return 0;
  35. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin 
Standard input is empty
stdout 
6
7
8
9
10
1
2
3
5
Min is 3
https://ideone.com/NSWNEG
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!