二分法

• 原理
• 模版
• 实践

原理

二分法：相较于顺序查找，二分法查找的不是单个元素，而是一个范围。利用数据中的规律不断的将搜索范围减半。

比如，猜数字游戏。

朋友让您在心目中想一个 1 − 1000 1-1000 1−1000 的数字，而后您问朋友问题，对方回答：

• Yes
• No

您最多也只要用 10 10 10 次一定能够猜出他心目中想的数字。

第一次只要问朋友是否小于 500 500 500，如果TA给出了肯定的答案，说明数字在 1 − 499 1-499 1−499 里面，第二次折半问TA这个问题即可。

类似地，如果TA的回答是否定的，说明对方心目中的数字是在 500 − 1000 500-1000 500−1000 之间，第二次往大了折半问即可。而后您不断缩小范围，每次减少一半，这样问 10 10 10 次即可，因为 2 2 2 的十次方等于 1024 1024 1024，大于 1000 1000 1000。

这就是二分查找。

但是，二分查找有一个问题，就是所有的数据事先要排序，而排序是有成本的。相比查找，排序的速度要慢得多。因此，是否应该对数据先花点时间进行一次排序，则要看具体应用的情况而定。

• 如果只对数据进行一次查找，为此事先进行排序显然就不合算了，只有当查找的次数足够多，通过次数抵消掉它的边际成本，为此花一些时间排序才合算。当然，这个场景有一个前提，就是数据是静态的，比如大学的数据库在进行学籍管理时，每一个年级新生入校后，人员是稳定的，对他们按照学号进行一次排序就有意义。再比如，对于历史数据，比如公司的营收，一旦形成，就是事实，不能修改的，这样做也有意义。

• 在大部分现实生活的应用中，数据总是在变化的，比如一个公司的员工，每个月有新的进来，老的离开。再比如一个人开车时，位置是不断变动的，周围加油站离他的距离也是变化的。在这种情况下，找一个目标是否要对所有的目标先排序，就值得商榷了。

在这种情况下，依然有办法做到利用原来数据有序的特点，动态调整新数据的，让每次排序所做的工作不要太多，需要使用一种叫“堆”的数据结构。

模版

int binary_search(int key, int *arr, int len){
	// 边界判断，防止翻车
	if(len <= 0)
		return -1;
		
	int low = 0;                      // 指向 arr 第一个元素，可改为 size_t 类型
	int high = len-1;                 // 指向 arr 最后一个元素，可改为 size_t 类型
	
	while(low <= high){
		int mid = (low + high) / 2;   
		// 防止 low + high 溢出的写法，可以换一种写法：生成 low ~ high 之间的数公式 : (high-low+1)+low
		// 改成这样：mid = low + (high - low + 1) / 2;
		// 主流编译器都会将 /2 转换成位运算 >>1，这是编译器内部的优化。因此我们没有必要手动去做这一步优化，写代码的时候还是写 /2。
		// 毕竟，还会产生运算符优先级问题、可读性也会差点。
		if(key < arr[mid])            // 小则去前半部分继续查找
			high = mid - 1;
		else if(key > arr[mid])       // 大则去后半部分继续查找.
			low = mid + 1;
		else
			return mid;
	}
	return -1;
}

• 初始条件： l o w = 0 ,   h i g h = a r r . l e n g t h − 1 low = 0,~high=arr.length-1 low=0, high=arr.length−1
• 终止条件： l o w > h i g h low>high low>high
• 向左查找： h i g h = m i d − 1 high=mid-1 high=mid−1
• 向右查找： l o w = m i d + 1 low=mid+1 low=mid+1

一般我们操作数组，也是左闭右开区间。

for( int i = 0; i < len; i++ )
	do sth...

因为，左闭右开用来表达各种操作和算法的边界会简洁清晰很多

S T L STL STL 中所有算法的处理多是左闭右开区间 [ b e g i n , e n d ) [begin, end) [begin,end)。

除了代码风格外，一般是算法方面的原因。

分治算法，如果一个左闭右开区间 [ x , y ) [x,y) [x,y)，子区间可以分解为 [ x , y 0 ) ,   [ y 0 , y 1 ) ,   [ y 1 , y 2 )   . . .   [ y n , y ) [x,y0),~[y0,y1),~[y1,y2)~...~[yn,y) [x,y0), [y0,y1), [y1,y2) ... [yn,y)，父子同构，天然适合分治实现。

在整数范围内，如果非要写为左闭右闭区间，也是可以的。 [ x , y ] [x,y] [x,y] 分解的子区间为 [ x , y 0 − 1 ] ,   [ y 0 , y 1 − 1 ] ,   [ y 1 , y 2 − 1 ]   . . .   [ y n , y ] [x,y0-1],~[y0,y1-1],~[y1,y2-1]~...~[yn,y] [x,y0−1], [y0,y1−1], [y1,y2−1] ... [yn,y]。

但是无论怎么分，总有一个区间和其他不同，划分偏左或偏右一个元素，划分是不整齐的。要打各种边界处理补丁来弥补。

所以，二分查找还有另外一个变种，用左闭右开的区间来实现。

• 初始条件： l o w = 0 ,   h i g h = a r r . l e n g t h low = 0,~high=arr.length low=0, high=arr.length
• 终止条件： l o w = = h i g h low==high low==high
• 向左查找： h i g h = m i d high=mid high=mid
• 向右查找： l o w = m i d + 1 low=mid+1 low=mid+1

只有加一，没有减一。

#include <iostream>
using namespace std;

template <typename T>
int binary_search_array(const T& key, const T arr[], int N) {
  if (N <= 0)
    return -1;
    
  int low = 0;
  int high = N;
  while (low < high) {
    int mid = low + (high - low + 1) / 2;
    if (key < arr[mid])		     // 小则去前半部分继续查找.
      high = mid;
    else if (key > arr[mid])	// 大则去后半部分继续查找.
      low = mid + 1;
    else
      return mid;
  }
  return -1;
}

int main() {
  int a[5] = {1, 2, 3, 4, 5};
  cout << binary_search_array(2, a, 5) << endl;
  return 0;
}

如果是算法，通常左闭右开都是用迭代器来实现：

// 使用迭代器, 描述更清晰
#include<iostream>
#include<vector>
using namespace std;

template <typename T, typename iterator>
bool binary_search_iterator(const T& key, iterator L, iterator H) {
  while (L < H) {
    iterator M = L + (H - L + 1) / 2;
    if (key < *M)       // 小则去前半部分继续查找.
      H = M;
    else if (*M < key)  // 大则去后半部分继续查找.
      L = M + 1;
    else
      return true;
  }
  return false;
}

int main() {
  vector<int> v = {1, 2, 3, 4, 5};
  cout << binary_search_iterator(2, v.begin(), v.end()) << endl;
  return 0;
}

 
二分查找还有可能查找到多个 key，但题目只要其中一个：

• 第一个值等于 key 的索引

// 查找第一个值等于 key 的索引
int first_equals(int key, int* arr, int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;   
        // 不加 1（上取整变成下取整），如果加 1 会死锁（一直循环）
        // 下取整找不到右边界，上取整找不到左边界，所以如果是查找左边界就是下取整，查找右边界就是上取整
        if (arr[mid] < key) 
        	l = mid + 1;
        else 
        	r = mid; 
    }
    
    if (arr[l] == key && (l == 0 || arr[l - 1] < key)) 
    // 结尾做一下处理：第一个值
    	return l;	
    return -1;
}

int main() {
  int v[] = {1, 2, 2, 4, 5};
  cout <<  first_equals(2, v, 5) << endl;
  return 0;
}

• 最后一个值等于 key 的索引

// 查找最后一个值等于 key 的索引
int last_equals(int key, int* arr, int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;  
        if (arr[mid] > key) 
        	r = mid - 1;
        else 
        	l = mid; 
    }
    
    if (arr[l] == key && (l == N - 1 || arr[l + 1] > key)) 
    // 结尾做一下处理：最后一个值
    	return l;
    return -1;
}

int main() {
  int v[] = {1, 2, 2, 4, 5};
  cout <<  last_equals(2, v, 5) << endl;
  return 0;
}

• 第一个大于等于 key 的索引

// 查找第一个大于等于 key 的索引
int first_large_or_equals(int key, int* arr, int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;   
        // 不加 1（上取整变成下取整），如果加 1 会死锁（一直循环）
        // 下取整找不到右边界，上取整找不到左边界，所以如果是查找左边界就是下取整，查找右边界就是上取整
        if (arr[mid] < key) 
        	l = mid + 1;
        else 
        	r = mid; 
    }
    if (arr[l] >= key && (l == 0 || arr[l - 1] < key))  
    // 结尾做一下处理：第一个>=
    	return l; 
    return -1;
}

int main() {
  int v[] = {1, 2, 2, 4, 5};
  cout <<  first_large_or_equals(2, v, 5) << endl;
  return 0;
}

• 最后一个小于等于 key 的索引

// 查找最后一个小于等于 key 的索引
int  last_less_or_equals(int key, int* arr, int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        if (arr[mid] > key) 
        	r = mid - 1;
        else 
        	l = mid; 
    }
    
    if (arr[l] <= key && (l == N - 1 || arr[l + 1] > key))  
    // 结尾做一下处理： 最后一个<=
    	return l; 
    
    return -1;
}

int main() {
  int v[] = {1, 2, 2, 4, 5};
  cout <<  last_less_or_equals(2, v, 5) << endl;
  return 0;
}

 
对于这些问题，应该采用左闭右开到区间：while(left < high)。

实践

Leetcode 上的二分法解决的问题类型，大概有三种：

• 在数组中查找符合条件的元素的索引

• 在一个有上下界的区间里搜索一个整数

• 判别条件是一个函数