二分查找，显而易见就是每次一分为二的查找方式。其先决条件为必须要在数组中实现，且查找的数据必须已经排序完毕。

首先我们来看一个二分查找库函数的实现：

C语言 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 
 * @param key 需要查找的元素
 * @param base 查找数组
 * @param n 数组大小
 * @param elemSize 数组元素字节数 
 * @param cmpfn 比较函数
 * @return 
 */

void* BSearch(void* key, void* base, int n, int elemSize, int (*cmpfn) (void*, void*)) {
	int left = 0, right = n;
	while (left <= right) {
		int mid = left + (right - left)/2;
		void* elemAddr = (char*) base + mid*elemSize;
		int tmp = cmpfn(key, elemAddr);
		if (tmp == 0) {
			return elemAddr;
		} else if (tmp < 0) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return NULL;
}

说明：

  • left + (right - left)/2

    此种写法为防止 left + right 的值过大而溢出，所以采用此种写法

写一个函数 LowerBound，在包含 size 个元素的、从小到大排序的 int 数组 a 里查找比给定整数 p 小的，下标最大的元素。找到则返回其下标，找不到则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int LowerBound(int a[],int size,int p) {
    int L = 0; 
    int R = size - 1; 
    int lastPos = -1; //到目前为止找到的最优解
    while( L <= R) {
        int mid = L+(R-L)/2;
        if(a[mid] >= p)
            R = mid - 1;
        else {
            lastPos = mid;
            L = mid + 1;
        }
    }
    return lastPos;
}

说明：

1
lastPos = mid;	L = mid+1;

如上 else 中语句，执行时 mid 处数组的值小于p，所以先将其中的最大值 mid 的下标给 lastPos ，然后寻找比 mid 处值大而比p的值小的数，所以将 mid+1 作为左端点继续操作。

练手

题目：

求下面方程的一个根：\(f(x) = x^3-5x^2+10x-80 = 0\)，若求出的根是a，则要求 \(|f(a)| \le 10^{-6}\)

解法：

对 \(f(x)\) 求导，得 \(f'(x)=3x^2-10x+10\) 。

由一元二次方程求根公式知方程 \(f'(x)= 0\) 无解，因此 \(f'(x)\) 恒大于0。

故 \(f(x)\) 是单调递增的。易知 \(f(0) < 0\) 且 \(f(100)>0\) ,所以区间 \([0,100]\) 内必然有且只有一个根。由于\(f(x)\)在 \([0,100]\) 内是单 调的，所以可以用二分的办法在区间 \([0,100]\) 中寻找根。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
double EPS = 1e-6;

double f(double x) {
    return x*x*x - 5*x*x + 10*x - 80;
}

int main() {
    double root, x1 = 0, x2 = 100,y;
    root = x1+(x2-x1)/2;
    int triedTimes = 1; //记录一共尝试多少次，对求根来说不是必须的
    y = f(root);
    while(fabs(y) > EPS) {
        if(y > 0)
            x2 = root;
        else
            x1 = root;
        root = x1+(x2 - x1)/2;
        y = f(root);
        triedTimes ++;
    }
    printf("%.8f\n",root);
    printf("%d",triedTimes);
    return 0;
}

说明：

循环条件：fabs(y) > EPS 也就是在精度值达到之后结束循环。