先找到翻转的起始下标,通过判断nums[0]
与target
的相对大小来决定在哪一段上进行常规二分。
class Solution { public: int binary_s(vector<int> nums, int target, int left, int right) { while(left <= right) { int middle = left + (right - left) / 2; if(nums[middle] == target) return middle; else if(nums[middle] < target) left = middle + 1; else if(nums[middle] > target) right = middle - 1; } return -1; } int search(vector<int>& nums, int target) { int move = 0, len = nums.size(); for(int i = 0; i < len - 1; i++) if(nums[i] > nums[i + 1]) move = i + 1; if(move == 0) return binary_s(nums, target, 0, len - 1); if(nums[0] > target) return binary_s(nums, target, move, len - 1); else return binary_s(nums, target, 0, move - 1); } };