21天算法打卡系列（4）

活动地址：CSDN21天学习挑战赛

今天的内容是折半查找，也就是二分查找。

二分查找的原理

二分查找就是在一个给定的有序区间内找一个值，每次找中间值根据中间值推断两边的数据属性，然后舍弃一半的区间，这样每次查找就可以减少一半的数据，时间复杂度是O(logN).
二分查找经常是应用于数组，是因为数组具有有随机访问的特点，并且数组是有序的。二分查找体现的数学思想是「减而治之」，可以通过当前看到的中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果，当然二分查找并不一定非要是有序数组，只要是可以通过中间元素来排除掉一半的区间都可以使用二分查找。

二分基础代码

下面来看一下基本的二分查找的代码和通用的二分查找的代码。

int main()
{
	int arr[] = { -1,0,3,5,9,12 };
	int target = 9;
	int n = sizeof(arr) / sizeof(arr[0]);
	int l = 0, r = n - 1;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (arr[mid] > target)
			r = mid - 1;
		else if (arr[mid] < target)
			l = mid + 1;
		else
		{
			printf("%d ", mid);
			break;
		}
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这段代码是二分查找的基础写法，在一个有序数组中查找一个数字，找到了就打印出来下标找不到就不打印。
根据中间值mid和target的大小关系我们可以判断出来target位于mid的左边还是右边。然后来变换l和r的这个区间，直到找到了target或者没找到但是l >= r，跳出循环。

二分通用代码

二分查找除了查找数组内的值，一般还有查找大于等于target的最小值，和小于等于target的最大值的下标。而一般所有的二分查找的题目都可以转换成上面的这两种题型或者是这两种题型的综合。下面就来看一下这两个题型对应的代码。

//查找大于等于target的最小值
int binFind(int* arr,int l,int r,int target)
{
    while(l<r)
    {
        
        int mid = l+r>>1;
        if(arr[mid]>= target)
            r = mid;
        else 
            l = mid+1;
    }
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

下面的代码就是查找小于等于target的最大值

int binFind(int* arr,int l,int r,int target)
{
    while(l<r)
    {
        int mid = (l+r+1)>>1;
        if(arr[mid] <= target)
            l = mid;
        else 
            r = mid-1;
    }
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12

下面解释一下这里的mid的取值这里可以将二分查找的区间看作是左右的红色和蓝色的两个区间，如下图

二分查找就是找到这个边界，左边界就是小于等于target的最大值，右边界就是大于等于target的最小值。这里可以看到两段代码的区别首先是如果是在左边也就是红色区间内查找的时候mid的取值是+1向上取整的，这样是防止死循环。
死循环的原因就是如果mid处的值就是target，此时满足条件<=target然后l = mid 此时l是没有变换的，再次求mid就会死循环（因为l和r此时是相等的），如果向上取整，第一次求mid的时候 r = l+1，mid = （l + r +1）/ 2 结果就是l + 1，由此就会使得r = mid -1 ，l和r 相等，跳出循环。

这就是二分查找