常用的在二分查找中节省时间的小技巧

那就是在计算mid的时候，不再使用(left right)/2而是(left right)>>1，>>是位运算符，学习过计算机组成原理的朋友都知道，位运算要比加法运算快得多，而右移一位就相当于除以2，举个例子，二进制数1000代表十进制数8，右移一位变成了0100，也就是十进制数4。

又一道LeetCode算法题奉上：

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

这道题是在说，一个原本有序的数组，有可能某处之前的元素按照原来的顺序放在了数组的末尾，然后在这样一个数组中查找值target。

同样是一个毫无疑问无序但又部分有序的数组，它的整体走向如下图所示：

我们首先要做的，仍然是找到峰值，只要找到峰值就能把数组划分成有序的两部分，那么问题来了，要如何找到峰值呢？

显然这道题目不能通过单调趋势确定峰值的位置，因为两部分都是单调递增的，但是我们知道左半部分的最小值和右半部分的最大值，左半部分的最小值就是数组的第一个元素，右半部分的最大值就是数组的最后一个元素。

遇到一个元素只要它不是峰值：

如果它小于右半部分的最大值，峰值就位于它的左边；

否则，峰值就位于它的右边。

如果它是峰值，此时有两种情况：

它是第一个元素，只要它大于它右边的元素它就是峰值；

它不是第一个元素，只要它大于它左右两边的元素它就是峰值。

在这个题中，还直接根据target推得target只可能位于数组的那一部分：只要大于等于左半部分的最小值就肯定位于左半部分；

只要小于等于右半部分的最大值就肯定位于右半部分。

剩下的就是简单二分查找了。

以下代码为通过该题的代码：

class Solution {
public:
vector<int> nums;
int len;
int rvalue;
int left,right;
intfindSummit
{
while(left<=right)
{
int mid=(left right)>>1;
if((mid==0&&mid 1<len&&nums[mid]>nums[mid 1])||(mid-1>=0&&mid 1<len&&nums[mid]>nums[mid-1]&&nums[mid]>nums[mid 1]))
{
return mid;
}
else if(nums[mid]<rvalue)
{
right=mid-1;
}
else
{
left=mid 1;
}
}
return -1;
}
intsearch(vector<int>& nums, int target) {
this->nums=nums;
len=nums.size;
if(len==0)
{
return -1;
}
//右半部分最大值
rvalue=nums[len-1];
left=0;
right=len-1;
int summit=findSummit;
if(target>rvalue)
{
//在左半部分
left=0;
right=summit;
}
else
{
//在右半部分
left=summit 1;
right=len-1;
}
while(left<=right)
{
int mid=(left right)>>1;
if(target==nums[mid])
{
return mid;
}
else if(target<nums[mid])
{
right=mid-1;
}
else
{
left=mid 1;
}
}
return -1;
}
};