责编 | 刘静
出品 | CSDN（ID：CSDNnews）
二分查找也叫折半查找 ( Binary Search ) ，是一种时间复杂度为 O ( logn ) ，因为它可以每次都将查找范围缩小为原来的一半。它要求查找序列要有序。然而这里所说的 " 有序 "，你真正理解了吗？
数字的二分查找
先描述一下最简单的二分查找算法：
先设返回值为 -1，如果找不到的话就返回 -1。
设置两个指针，left 和 right，left 最开始指向第一个元素的下标，right 最开始指向最后一个元素的下标，每次查找都要找到中间值值的下标 mid= ( left+right ) /2，让中间值 arr [ mid ] 跟查找值 target 进行比较。
如果查找值 target 等于中间值 arr [ mid ] ，这说明找到了查找值 target，直接返回 mid 作为查找值 target 的下标；
如果查找值 target 小于中间值 arr [ mid ] ，这说明查找值 target 如果存在的话一定位于中间值的左边，因此我们将 right 置为 mid-1，这样下次需要查找的序列就变成了从 left 到 mid-1；
如果查找值 target 大于中间值 arr [ mid ] ，这说明查找值 target 如果存在的话一定位于中间值的右边，因此我们将 left 置为 mid+1，这样下次需要查找的序列就编程了从 mid+1 到 right。
如此循环，直到 left>right 结束。
简单二分查找的代码：
int binarySearch ( int target )
{
int ret=-1;
int len=arr.size ( ) ;
int left=0;
int right=len-1;
while ( left<=right )
{
int mid= ( left+right ) /2;
if ( target==arr [ mid ] )
{
ret=mid;
break;
}
else if ( target<arr [ mid ] )
{
right=mid-1;
}
else
{
left=mid+1;
}
}
return ret;
}
看一个最简单的二分查找的例子：
查找值：target=3
下面开始二分查找，橙色部分为 left，黄色部分为 right，绿色部分为 mid。
查找值：target=79
还可以针对什么进行二分查找呢？
英文有 26 个字母，按照 abc...xyz 的顺序排列，这就使得字母有了顺序，也就使得字符串有了字典序 ( alphabetical order ) 。
所谓字典序，就是指两个字符串从前往后挨个字符比较，如果出现字符串 str1 的某一位上的字母在字母表中排在字符串 str2 的相同位的字母的前面，则称 str1<str2。举个简单的例子，"bicycle" 和 "binary"，'b' 和 'i' 都是相同的，比到第三位的时候，'c' 在字母表中的顺序排在 'n' 的前面，因此 "bicycle" 小于 "binary"。还有一种特殊情况，就是一直比较比到其中有一个字符串没有字母可以比较时，短的字符串就小于长的字符串。再举个简单的例子，"alpha" 和 "alphabetical"，"alpha" 就小于 "alphabetical"。
读到这里，我可以跟大家坦白了，以上的仅仅是二分查找的开胃菜。
二分查找能否用于 " 看似无序 " 的序列
一道 LeetCode 算法题奉上：
https://leetcode-cn.com/problems/find-in-mountain-array/
这道题是在说，在一个数组中，它的元素中存在一个峰值，峰值左右两边的元素都比它小，然后给出一个查找值 target，让你找到元素值等于 target 的最小下标，如果没有就返回 -1。
峰值左边的元素由小到大排列，峰值右边的元素由大到小排列，整个数组毫无疑问是无序的，但是部分有序的，如下图所示：
细心的朋友已经发现了：
如果遇到一个元素，它的左边元素比它小，右边元素比它大，那么峰值一定在它的右边；
如果遇到一个元素，它的左边元素比它大，右边元素比它小，那么峰值一定在它的左边；
如果遇到一个元素，它的左边元素比它小，右边元素也比它小，那么它就是峰值！
根据以上规律，就可以写一个二分查找峰值的算法了。
int findSummit ( vector<int> arr )
{
int len=arr.size ( ) ;
int left=0;
int right=len-1;
while ( left<=right )
{
int mid= ( left+right ) /2;
int pre=arr [ mid-1 ] ;
int now=arr [ mid ] ;
int aft=arr [ mid+1 ] ;
if ( pre<now&&now>aft )
{
return mid;
}
else if ( pre<now&&now<aft )
{
// 峰值在右边
left=mid+1;
}
else
{
// 峰值在左边
right=mid;
}
}
return -1;
}
这里与简单二分查找略有不同的是峰值如果在左边 right 置为 mid 而不是 mid-1，这是为了防止数组越界，大家可以思考一下为什么，本文主要介绍二分思想就不再过多介绍了。
找到了峰值的位置（下标），我们再去找 target 就易如反掌了，可以直接套用简单二分查找算法的模板。既然题目要求找到等于 target 的元素的最小下标，我们就先找左边，即 [ 0,summit ] ；再找右边，即 [ summit,len-1 ] 。summit 为峰值下标，len 为序列长度。
以下代码为通过该题的代码：
/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get ( int index ) ;
* int length ( ) ;
* };
class Solution {
public:
int findInMountainArray ( int target, MountainArray &mountainArr ) {
int len=mountainArr.length ( ) ;
int left=0;
int right=len-1;
int summit=-1;
int mid=-1;
while ( left<=right )
{
mid= ( left+right ) >>1;
int pre=mountainArr.get ( mid-1 ) ;
int now=mountainArr.get ( mid ) ;
int aft=mountainArr.get ( mid+1 ) ;
if ( pre<now&&now>aft )
{
summit=mid;
break;
}
else if ( pre<now&&now<aft )
{
left=mid+1;
}
else
{
right=mid;
}
}
left=0;
right=summit;
while ( left<=right )
{
mid= ( left+right ) >>1;
int now=mountainArr.get ( mid ) ;
if ( target==now )
{
return mid;
}
else if ( target<now )
{
right=mid-1;
}
else
{
left=mid+1;
}
}
left=summit;
right=len-1;
while ( left<=right )
{
mid= ( left+right ) >>1;
int now=mountainArr.get ( mid ) ;
if ( target==now )
{
return mid;
}
else if ( target>now )
{
right=mid-1;
}
else
{
left=mid+1;
}
}
return -1;
}
那就是在计算 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;
int findSummit ( )
{
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;
}
int search ( 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;
}
}
retur -1;
}
二分查找不仅仅适用于有序的序列，在部分有序、有规律可循的序列中查找值也可以使用二分查找，只要可以将搜索区域不断缩小，就可以想到二分查找。
作者简介：Cooper Song，大学计算机专业在校生，本科在读，学生开发者。
声明：本文系作者独立观点，不代表 CSDN 立场。
