題目描述

整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值 互不相同 。

在傳遞給函數(shù)之前，nums 在預(yù)先未知的某個下標(biāo) k（0 <= k < nums.length）上進行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標(biāo) 從 0 開始 計數(shù)）。例如， [0,1,2,4,5,6,7] 在下標(biāo) 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。

給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個整數(shù) target ，如果 nums 中存在這個目標(biāo)值 target ，則返回它的下標(biāo)，否則返回 -1 。

你必須設(shè)計一個時間復(fù)雜度為 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

示例 3：

輸入：nums = [1], target = 0
輸出：-1

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums 中的每個值都 獨一無二
• 題目數(shù)據(jù)保證 nums 在預(yù)先未知的某個下標(biāo)上進行了旋轉(zhuǎn)
• -104 <= target <= 104

解答

class Solution {
public:// 采用二分法int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while(l <= r){int mid = (l + r) >> 1;if(target == nums[mid]) return mid;// 旋轉(zhuǎn)后產(chǎn)生左右兩個升序序列// l ~ mid 都在左邊的升序序列中if(nums[l] <= nums[mid]){// 范圍確定在[l, mid)if(target >= nums[l] && target < nums[mid]) r = mid - 1;// target < nums[l] || target >= midelse l = mid + 1;}else // l~mid 一部分在左邊，一部分在右邊{if(target > nums[mid] && target <= nums[r]) l = mid + 1;else r = mid - 1;}}return -1;}int search1(vector<int>& nums, int target) {vector<int>::iterator iter = find(nums.begin(), nums.end(), target);return iter != nums.end() ? iter - nums.begin() : -1;}
};