33.SearchinRotatedSortedArray.md

33. 搜索旋转排序数组

1. 描述

   • 来源：领扣62，力扣33
   • 现有升序数组在未知某点上进行了旋转。(例如[0,1,2,4,5,6,7]变为[4,5,6,7,0,1,2])。
   • 数组中不存在重复的元素。
   • 给定一个数字target，如果数组中能找到，则返回target的下标，否则返回-1。
   • 示例:
     • 输入: nums = [4,5,6,7,0,1,2], target = 0
     • 输出: 4

2. 思路：

   • 根据题意，数组是两个升序序列，可以表示为以下形状。通过和nums[0]比较，可以判断查找区间在左边还是右边。

       -
      -
     -
          -
         -
        -
     

   • 定位查找区间分为三种情况。mid和target在同一边；target在左mid在右；target在右mid在左。
   • 注意，nums[left]的访问是O(n)复杂度。每次和它比较导致“Time Limit Exceeded”
   • 所以改成与nums[0]比较。

3. 实现

   class Solution {
   public:
       int search(vector<int>& nums, int target) {
           int left=0, right=nums.size()-1;
           int mid;
           while(left <= right)
           {
               mid = left + (right-left)/2;
               if(nums[mid]==target)
                       return mid;
               // 情况1，mid和target在同一侧
               if((nums[mid]>=nums[0] && target>=nums[0])||(nums[mid]<nums[0] && target<nums[0]))
               {
                   if(nums[mid]==target)  return mid;
                   if(nums[mid] < target) left = mid+1;
                   else right = mid-1;                    
               }                
               // 情况2，target在左,mid 在右
               else if(target>=nums[0])  right = mid-1;            
               // 情况3，target在右,mid 在左
               else if(target<nums[0]) left = mid+1;
           }
           return -1;
       }
   };