1. 概要说明

Binary search is a fast search algorithm with run-time complexity of Ο(log n).

This search algorithm works on the principle of divide and conquer.

For this algorithm to work properly, the data collection should be in the sorted form.

二分查找的复杂度

2. 动图演示

3. 代码示例

#include<iostream>
using namespace std;

// if key found then return index of search key else return -1
int binarySearch(int arr[], int low, int high, int key) {
  int mid = 0;
      
  while(low <= high) {
    // find middle index
    mid = (low + high) / 2;

    // compare search key and middle term
    if (key == arr[mid])
        return mid;
    else if(key > arr[mid]) 
      low = mid + 1;
    else
      high = mid - 1; 
  }

  return -1; // key not found 
}

int main()
{
  int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
  int key = 80; // search key
  int size = sizeof(array)/sizeof(array[0]); // array size
  int index = binarySearch(array, 0, size, key);
  
  // display result
  if(index == -1)
    cout << key << " Not Found" << endl;
  else
    cout << key << " Found at Index = " << index << endl;

  return 0;
}

4. 编程

4.1 查找数值
  1. c011-1a 二分查找某个数
  2. c011-1 二分查找
  3. c011-2 查找最接近的元素
4.2 逼近求解
  1. c011-1b 求一个数的平方根（用二分法）
  2. c011-1c 求一个数的平方根（用牛顿法）
  3. c011-3 二分法求函数的零点
4.3 二分法求函数的零点的参考代码
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

double f_x(double x) //计算f(x)的值
{
    return pow(x,5) - 15 * pow(x,4) + 85 * pow(x,3) - 225 * pow(x,2) + 274 * x - 121;
}

double binary_search_fx(double left, double right)
{
    int last = -1; //上一次结果乘以10^6
    double mid = 0.0; 
    int diff = 0; //由于无法精确计算，通过和上一次f(x)的差值来确定是否已经非常接近了。
    
    do {
        mid = (left + right) / 2.0;
        double result = f_x(mid); //函数结果
        
        if(result==0.0){ 
            return result;
        }else if (result >0.0){ //f(x)是单调递减的，f(x)>0则表示x的值过小，去掉左半部分
            left = mid;
        }else{
            right = mid; //f(x)<0表示x的值过大，去掉右半部分
        }
        
        diff = round(result * 1000000) - last; //
        last = round(result * 1000000); 
    } while (diff !=0);

    return mid;
}

int main()
{
    cout << setiosflags(ios::fixed) << setprecision(6) << binary_search_fx(1.5, 2.4) << endl;
}

5. 真题练习

1、

【CSP 2019 入门组第一轮 q05】设有100个已排好序的数据元素，采用折半查找时，最大比较次数为（）
A. 7   B. 10   C. 6   D. 8  

2、

【NOIP 2017 普及组初赛 q28】完善程序：
（切割绳子） 有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段，求绳段的最大长度是多少。

输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过10610^{6}的正整数，表示每条绳子的长度，第三行是一个不超过10810^{8}的正整数 m。
输出：绳段的最大长度，若无法切割，输出 Failed。

#include<iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main()
{
    cin >> n;
    count = 0;
    for (i = 0; i < n; i++)
    {
        cin >> len[i];
        ①;
    }
    cin >> m;
    if (②)
    {
        cout << "Failed" << endl;
        return 0;
    }
    lbound = 1;
    ubound = 1000000;
    while (③)
    {
        mid = ④;
        count = 0;
        for (i = 0; i < n; i++)
            ⑤;
        if (count < m)
            ubound = mid - 1;
        else
            lbound = mid;
    }
    cout << lbound << endl;
    return 0;
}