題目:
整數數組 nums 按升序排列,數組中的值 互不相同 。
給你 旋轉后 的數組 nums 和一個整數 target ,如果 nums 中存在這個目標值 target ,則返回它的下標,否則返回 -1 。
思路:
此處采用容易理解的兩次二分查找法,確定target位置。
第一次先找到旋轉點用一次二分
第二次確定target在哪個區間之后再二分搜索
class Solution
{
public:int search(vector<int>& nums,int target){int L = 0, R = nums.size() - 1;// [)區間// 最后一個判斷的是最小值,即旋轉點// 第一次二分查找,確定最小值索引while(L < R){int mid = L + (R - L)/2;if (nums[mid] <= nums[R]){R = mid;}else{L = mid + 1;}}// 上述循環結束, R=L 都會指向最小值的索引// 確定target在哪個區間,更新左區間或右區間值int left, right;if(target >= nums[0] && R != 0 && target <= nums[R-1]){left = 0;right = R;}else{left = R;right = nums.size() - 1;}// 第二次二分查找,確定target索引while(left <= right){int mid = left + (right-left)/2;if(nums[mid] == target) return mid;else if(nums[mid] < target){left = mid + 1;}else{right = mid - 1;}}return -1;}
};
Leecode—153:尋找旋轉矩陣中的最小值
思路同上,取第一次二分查找即可。
class Solution {
public:int findMin(vector<int>& nums) {int L =0, R = nums.size()-1;// [)區間// 最后一個判斷的是最小值,即旋轉點// 一次二分查找,確定最小值索引while(L < R){int mid = L + (R-L)/2;if(nums[mid] <= nums[R]){R = mid;}else{L = mid + 1;}}// 返回值L=R都是最小值索引return nums[L];}
};