二分答案|LeetCoder 33. Search in Rotated Sorted Array(二分)

【二分答案|LeetCoder 33. Search in Rotated Sorted Array(二分)】是把一个升序的数组,前面的连续的一部分(可以是空)放在数组的后面,然后再这个数组这中找一个给出的值,数组中不存在重复的元素。
这个题目也是《剑指offer》二分查找的一道例题

class Solution { public: int search(vector& nums, int target) { int l = 0, r = nums.size()-1; while(l <= r) { int mid = l+r>>1; if(nums[mid] == target) return mid; if(target < nums[mid]) { if(nums[mid] < nums[r]) r = mid - 1; // 右半部分是有序的 else { // 否则 左边是有序的 //当目标值小于左边的所有元素, 说明只能在右端了 if(target < nums[l]) //(也就是左右端都是有序的, 但是目标值小于中间值,但是目标值却在数组中的右边) 例如2个数字,3 1 的时候 l = mid + 1; else r = mid - 1; } } else { if(nums[l] < nums[mid]) l = mid + 1; else { if(target > nums[r]) r = mid - 1; else l = mid + 1; } }} return -1; } };

    推荐阅读