• 介绍
• 基本思想
• 代码
  • 整数二分
  • 小数二分
• 时间复杂度

介绍

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列.

基本思想

对有序序列进行折半操作，逐渐缩小所要查找的数据范围.

二分查找相比于顺序查找更快速，时间复杂度从O(n)优化到O(logn).

这是整数二分，会有边界问题(中点mid=(l+r)/2分子什么时候加一，什么时候不加，要注意.

下面的代码对应的是acwing这道题.用二分法计算数据范围.

代码

整数二分

#include 
int op[100010];

int main() {
	int n, m;
	scanf("%d %d", &n, &m);//这是对应acwing上面的题目写的，不重要
	for (int i = 0; i < n; i++)
		scanf("%d", &op[i]);
	while (m--)
	{
		int x;
		scanf("%d", &x);
		int l = 0, r = n - 1;//左右指针
		while (l < r) 
		{
			int mid = (l + r) / 2;//中点值
			if (op[mid] >= x)
				r = mid;
			else
				l = mid + 1;
		}
		if (op[l] != x)
			printf("-1 -1");
		else {
			printf("%d ", l);
			int l = 0, r = n - 1;
			while (l < r) {
				int mid = (l + r + 1) / 2;//if下面是l时就+1
				if (op[mid] <= x)
					l = mid;
				else
					r = mid - 1;
			}
			printf("%d ", l);
		}
		printf("\n");
	}
	return 0;
}

小数二分

#include
int main()
{
    double n;
    scanf("%lf",&n);
    double l=0,r=n;
    while(r-l>1e-6)
    {
        double mid=(l+r)/2;
        if(mid*mid>=n)r=mid;
        else l=mid;
    }
    printf("%lf\n",l);
    return 0;
}

时间复杂度

每次将区间划分一半，需要logn次才能把区间划分到不可分割，同快排和归并的递归推导