二分查找的三种方法

二分查找，是在有序的前提下进行查找，时间复杂度为O（log2N）

二分不一定是非要单调性，但是单调性一定可以二分，左边区间满足某种特性；右边区间不满足某种特性。那么我们就能够通过二分法来寻找左区间的右端点或者右区间的左端点

前言

对于已经排好序的数组，快速的寻找到指定元素，并返回其下标，这个时候就有二分查找的妙用

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、二分查找是什么？

二分查找是一种算法，可以快速的找到有序数组指定数值。

第一步：while(l<=r)   进入这个while循环 ，l=0 , r=n-1(数组长度-1)  ，然后有 mid=(l+r)/2  得到中间值。  ----------数组为  arr

第二步：进行判断，如果输入的数值  x 大于 arr[ l ]  那么说明  x在mid 和 l 之间  那么改变 r 的数值 r=mid-1； 否则  l=mid+1

二、三种方法

1.第一种

第一种方法是上文所说的最常规的做法

当遇到重复的有序数组的时候，得到的是第一次出现这个元素的下标

//普通经典的二分查找  这个是用于有序数组的
//这个方法是有单调性这个硬性条件的，即----有序数组
 
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 7;//想要找到的元素   返回他下标
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz - 1;
	
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] > k) {
			right = mid-1;
		}
		else if (arr[mid] < k) {
			left = mid + 1;
		}
		else {
			printf("找到了，下标是：%d", mid);
			break;
		}
   }
	if (left > right) {
		printf("数组中不存在改数字~~、\n");
	}
	return 0;
}
 

2.第二种

分界为：【l，mid-1】【mid，r】

第二种方法 ， 是y总讲解的，第二种和第三种方法实际上差不多，只是mid是否+1的区别

第二种和第三种实质上差不多，最后返回 l  或者 r  都可以

原理：
在一组数组p【】中，先是自己输入一个数字比如x，然后在【l，r】区间内，找到mid=(l+r)/2
然后p【mid】与x比较，设定一个比较方法  比如大于等于x  为了找到最接近x的p【】数组中的元素
-l-------x---mid------r      mid的数值大于等于x  在x的右边满足那个判定要求  p[mid]>= x

然后改变区间【l，r】r=mid 得到 【l，mid】  
如果不满足的话 l-------mid----x------r 那就是变成 l=mid+1  【mid+1，r】
不需要+1   mid=l+r>>1;
这样整体为  true [l,mid]  false [mid+1,r]

另一种：
也是求数组中最靠近输入数值x 的最小的一个数

方法：
l--------x----mid----r  
根据已知，判断依据是要p【mid】<=x
所以 如果是 l--------x----mid----r  这样fasle  返回的范围为  r=mid-1  [l,mid-1]
如果是  l--------mid ------x----r   这样  true  返回的范围是 l=mid   [mid,r]

整体来看就是true [mid,r]  false [l,mid-1]
  需要+1    ------->  加一是因为当l=r-1 的时候  mid=l 这样范围是不变，又要再次循环
这样的话，mid=l+r+1>>1   

	int l = 0;
	int x = 0;
	int r = n - 1;
	scanf("%d", &x);
	while (l < r) {
		int mid = l + r +1>> 1;
		if (p[mid] <= x) {
			//要找的就是大于x的  如果满足的话 mid 在x左边缩小范围为  r=mid 【l，mid】
			l = mid;//l-----mid---x----r
		}
		else {
			r=mid-1;
		}
	}

3.第三种

分界为：【l，mid】【mid+1，r】  

所谓的是否  +1 我们主要看的是 if语句判断是<= 还是>=  如果是>= 的情况的话

l-----mid----x---r     满足p【mid】<=x   这样r返回的是  mid  即  r=mid  因为mid可以等于x

l-------x----mid---r   不满足 p【mid】<=x  这样的话 mid不等于x  所以 因为是整数二分（两个数之间间隔为1）所以r=mid-1；

	int l = 0;
	int x = 0;
	int r = n - 1;
	while (l < r) {
		int mid = l + r >> 1;
		if (p[mid] >= x) {
			r = mid;
		}
		else {
			l = mid+1;
		}
	}

三、测验三种方法的使用

1、第一种方法

这一种方法是用于单调递增数组的，当数组中出现重复的数字的时候，返回的下标就不知道是重复数字的哪一个了

---

2、第二种方法

当没有重复数字出现的时候，是和其他两种一样，当重复出现一个数字的时候，返回的是最后一次出现这个数字的下标

 

 

3、第三种方法

当没有重复数字出现的时候，是和其他两种一样，当重复出现一个数字的时候，返回的是第一次出现这个数字的下标

 

附加：浮点数二分

浮点数二分，不需要考虑边界的问题，判断条件根据题意来就可以

int main()
{  ///算法技巧：当要求r和l之间的数值差为  1e-6, 然后 可以限定为 r-l>1e-8  始终多两个保证精度
	double x;
	scanf("%lf", &x);
 
	double l = 0, r = x;
	//while (r - l > 1e-6) {
	//	double mid = (l+r)/2;
	//	if (mid * mid >= x) {  //设定一个满足的判断条件
	//		//l-----x------mid*mid----r
	//		r = mid;
	//	}
	//	else {
	//		//l----mid*mid----x---r
	//		l = mid;
	//	}
	//}
	for (int i = 0; i < 100; i++) {
		double mid = (l + r) / 2;
		if (mid * mid >= x) {
			//l-----x------mid*mid----r
			r = mid;
		}
		else {
			//l----mid*mid----x---r
			l = mid;
		}
	}
 
	//两种写法
	printf("%lf", l);
	return 0;
}
 

总结 

第二种和第三种实质上差不多，最后返回 l  或者 r  都可以，最经典的是第一种方法，第二种第三种更快一点。

while (l < r) {
        int mid = l + r +1>> 1;
        if (p[mid] <= x) {
            //要找的就是大于x的  如果满足的话 mid 在x左边缩小范围为  r=mid 【l，mid】
            l = mid;
        }
        else {
            r=mid-1;
        }
    }

这个里面的if语句中，r和l 返回什么都是依据这个 p[mid] <= x 是否相等  l=mid，的原因是mid不排除等于x的情况，所以区间l不能返回mid+1  只能是mid。r=mid-1  是因为 else的时候mid一定不等于x ，又因为是整数二分，即间隔为1 所以减一就可以  都是闭区间