text: //
  //  main.cpp
  //  Find Minimum in Rotated Sorted Array
  //
  //  Created by Yuhua Mai on 1/20/15.
  //  Copyright (c) 2015 Yuhua Mai. All rights reserved.
  //
  //Suppose a sorted array is rotated at some pivot unknown to you beforehand.
  //
  //(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
  //
  //Find the minimum element.
  //
  //You may assume no duplicate exists in the array.
  
  #include <iostream>
  
  #include <algorithm>
  #include <vector>
  
  using namespace std;
  
  class Solution {
  public:
      int findMin(vector<int> &num) {
          if(num.size() == 0) {
              return 0;
          }
          
          int l = 0;
          int r = (int)num.size() - 1;
          int min = num[0];
          
          while(l < r - 1) {
              int m = (l + r) / 2;
              
              if(num[l] < num[m]) {
                  min = std::min(num[l],min);
                  l = m + 1;
              } else if(num[l] > num[m]) {
                  min = std::min(num[m],min);
                  r = m - 1;
              } else {
                  l++;
              }
          }
          
          min = std::min(num[r],min);
          min = std::min(num[l],min);
          
          return min;
      }
  };
  
  int main(int argc, const char * argv[]) {
      int myints[] = {4, 5, 6, 7, 0, 1, 2};
  //    int myints[] = {4, 0, 1, 2, 3};
  //    int myints[] = {1, 1, 1, 1, 0, 1, 1};
  //    int myints[] = {0, 1, 1};
  //    int myints[] = {0, 1, 2, 3, 4, 5};
      vector<int> array(myints, myints + sizeof(myints) / sizeof(int));
      
      printf("findMin: %d\n", Solution().findMin(array));
      
      return 0;
  }
  