二分法類題-Leetcode33題-搜尋旋轉排序數組

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。

搜尋一個給定的目标值，如果數組中存在這個目标值，則傳回它的索引，否則傳回 -1 。

你可以假設數組中不存在重複的元素。

你的算法時間複雜度必須是 O(log n) 級别。

示例 1:

輸入: nums = [4,5,6,7,0,1,2], target = 0 輸出: 4 示例 2:

輸入: nums = [4,5,6,7,0,1,2], target = 3 輸出: -1

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題思路

區間有這麼幾種可能，全部升序，左側為升序區間右側為旋轉區間，左側為旋轉區間右側為升序區間。

是以在使用二分法時，要考慮到target的值在哪個區間裡

class Solution {
public:
    int search(vector<int>& nums, int target) {
       if(nums.size()==1)return target==nums[0]?0:-1;
       if(nums.size()==0)return -1;
       int begin=0;
       int end=nums.size()-1;
       while(begin<=end)
       {
           int mid=(begin+end)/2;
          if(target==nums[mid])return mid;
          if(nums[0]<=nums[mid])//左側為升序 右側為旋轉
          {
            if(target<nums[mid]&&target>=nums[0])//目标值在升序區間裡
            {
                end=mid-1;
            }
            else//否則在旋轉區間裡
            {
               begin=mid+1;
            }
          }
          else//左側為旋轉，右側為升序
          {
              if(target>nums[mid]&&target<=nums[nums.size()-1])//目标在升序區間裡
              {
                  begin=mid+1;
              }
              else//否則在旋轉區間裡
              {
                  end=mid-1;
              }
          }
       } 
       return -1;
    }
};