Search in Rotated Sorted Array

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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

解决此题，需要明确的是lb -> mid 或者mid->ub这两个部分，一定至少有一个是有序的

int search(vector<int> &nums, int target){
  if(nums.empty())   return -1;

  int lb = 0;
  int ub = nums.size() - 1;

  while(ub >= lb){
    int mid = (ub + lb)>>1;

    if(nums[mid] == target)   return mid;

    //左半部分有序，此处取得到等号(想想区间只有两个数的情况)
    if(nums[lb] <= nums[mid]){
      //此处为nums[lb] <= target
      if(nums[lb] <= target && target < nums[mid])
        ub = mid - 1;
       else
         lb = mid + 1;
    }
    //右半部分有序
    else{
      if(nums[mid] < target && target <= nums[ub])
        lb = mid + 1;
       else
         ub = mid - 1;
    }
  }

  return -1;
}