二分查找解决旋转数组
二分查找用到很多大于小于号, 每次都得判断是否需要加等于, 着实费劲..
题目很容易理解, 也可以快速想出思路:
因为数组旋转前是有序的, 所以旋转后会保持一定的有序性, 可以对有序部分进行二分查找或缩小查找查找范围.
举个例子:
如果原数组为: 2 5 6 7 0 1 . 数组最左端的值为2, 第一轮num[mid]值为6, 下标从0到 mid 所对应的值有序,
如果num[start]<=target<num[mid], 就去mid前半部分继续找, 否则去后半部分找.
如果原数组为: 2 5 6 0 1 2 . 数组最左端的值为2, 第一轮num[mid]值为0, 下标从 mid 到 last-1 所对应的值有序,
如果num[mid]<target<=num[last-1], 就去mid前半部分继续找, 否则去后半部分找.
如果是 1 1 1 1 0 1 1 . num[start] == num[mid],
那直接让 start+1, 去掉这个干扰项, 可以保证不影响旋转数组原来的有序性质.
代码1:
public:bool search(vector<int>& nums, int target) {int size = nums.size();int first = 0;int last = size;while(first < last){int mid = first + (last - first)/2;if(nums[mid] == target){return true;}if(nums[first] < nums[mid]){if(nums[first]<= target &&target < nums[mid])last = mid;elsefirst = mid+1;}else if(nums[first] > nums[mid]){if(nums[mid] < target &&target <= nums[last-1] )first = mid+1;elselast = mid;}else if(nums[first] == nums[mid]){first++;}}return false;}
这里的难点是判断哪里需要加"="号,
根据上述分析可以先写出代码结构
public:bool search(vector<int>& nums, int target) {// ... 省略while(first < last){int mid = first + (last - first)/2;if(nums[mid] == target){return true;}if(nums[first] < nums[mid]){// ??? block1}else if(nums[first] > nums[mid]){// ??? block2}else if(nums[first] == nums[mid]){first++;}}return false;}
首先可以先构想一个示例,
2 5 6 7 8 0 1
mid 第一次代表的值为7, 如果 target 落在了 2 和 7 之间, 那就可以把搜索区间缩小到 first 到 mid 部分, 否则就缩小到 mid+1 和 last 之间 (左开右闭原则)
所以 block1 部分的代码:
if(nums[first] <= target && target < nums[mid])last = mid;elsefirst = mid+1;
为什么 nums[first] <= target 要加等于号, 而 target < nums[mid]) 不加?
因为如果 target 落在 mid 的左半部分时, nums[first] 这个数字一定会参与到下一次的二分查找, 必须保证包含nums[first]这个数字, 所以nums[first] <= target 要加等于号.
而 target 是否等于 nums[mid] 这个条件已经在
if(nums[mid] == target){ return true; }
判断过了, 所以不用判断 target 是否等于 nums[mid] .
再构想一个示例,
2 5 0 1 1 2 2
mid 第一次代表的值为1, 如果 target 落在了 1 和 2 之间, 那就可以把搜索区间缩小到 mid+1 到 last 部分, 否则就缩小到 first 和 mid 之间.
所以 block2 部分的代码:
if(nums[mid] < target && target <= nums[last-1] )first = mid+1;elselast = mid;
为什么 target <= nums[last-1] 要加等于号, 而 nums[mid] < target 不加?
因为如果 target 落在 mid 的右半部分时, nums[last-1] 这个数字一定会参与到下一次的二分查找, 必须保证包含nums[last-1]这个数字, 所以nums[first] <= target 要加等于号.
target 是否等于 nums[mid] 这个条件如上所述, 已存在, 不用判断.
=======================
按理说到这里可以结束了, 已经写出了一份标准代码.
但是如果第一层思路稍有不同, 也可以写出一份效果完全一样的代码.
如果写出框架时不是比较 nums[first] 和 nums[mid] 的关系,
而是比较 nums[first] 和 nums[mid] 的关系, 写出如下框架:
if(nums[mid] < nums[last-1]){// ???}else if(nums[mid] > nums[last-1]){// ???}else if(nums[mid] == nums[last-1]){// ???}
判断思路与上同理, 可以自行试写.
完整代码如下:
public:bool search(vector<int>& nums, int target) {int size = nums.size();int first = 0;int last = size;while(first < last){int mid = first + (last-first) /2 ;if(nums[mid] == target){return true;}if(nums[mid] < nums[last-1]){if(nums[mid] < target && target <= nums[last-1]){first = mid + 1;}else{last = mid;}}else if(nums[mid] > nums[last-1]){if(nums[first] <= target && target < nums[mid]){last = mid;}else{first = mid + 1;}}else if(nums[mid] == nums[last-1]){last--;}}return false;}