算法提升（一）二分法

作者：@小萌新
作者介绍： 非科班大二学生 希望自己能每天输出优质内容
专栏：算法提升之路
由于作者水平有限 所以博客中难免会出现纰漏 希望大佬们看到之后可以指正！> 我们能把握的只有现在 要专心！

一. 二分法的介绍

1. 有序数组中找一个值

题目给你一个有序的数组 要你在这个数组中找一个值 并且返回它的下标 如果找不到就返回-1

这个题目就是一个经典的二分查找运用问题

想一想 假如说给了我们一个有序的数组 我们从头到尾遍历的话 最差的情况下是怎么才会找到这个数呢？

是不是这个数在末尾的时候啊 这个时候的时间复杂度是O（N）

那么这个时候就可以用到我们的二分法了

既然说这个数组是有序的 我们假设是这样子

我们从中间开始找

假设这个8是我们的要找的元素的话 我们直接返回这个下标就可以了

假如不是的话 我们比较下这个数和我们要找的数的大小

如果这个数大于我们要找的数 是不是整个数组的右边我们就不要了啊
如果这个数小于我们要找的数 是不是整个数组的左边我们就不要了啊

这样每次减少一半是不是时间复杂度就是Log（N）啊

之后我们继续重复这个过程

直到我们的左下标大于我们的右下标的时候是不是就表明我们要找的这个数不存在啊

我们来看看代码是怎么表示的

int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 0;
	cin >> k;
	// 设置左右下标
	int left = 0;
	int right = sz - 1;
	// 循环二分查找
	int mid = 0;
	while (left<=right)
	{
		// mid = (left + right) /2  防止溢出 
		mid = left + (right - left) / 2;
		// 判断是否是否等于我们要找的值
		if (arr[mid]== k)
		{
			cout << mid;
			break;
		}
		else
		{
			if (arr[mid]>k)
			{
				right = mid - 1;
			}
			else
			{
				left = mid + 1;
			}
		}
	}

	return 0;
}
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
27
28
29
30
31
32
33
34
35
36

代码也是很简单 简单写一下就可以了

这里注意的有一点

就是关于mid的变化

		// mid = (left + right) /2  防止溢出 
		mid = left + (right - left) / 2;
1
2

此外还可以试试这种写法

	    // mid = (left + right) /2  防止溢出 
		mid = left + ((right - left) / 2 >> 1);
		// 向左移一位 其实就是相当于除以2
1
2
3

2. 寻找有序数组中大于某个数的位置

给你一个有序数组 要求你找到从某个值开始 后面的所有值都大于我们的key值

这道题目也是一个经典的二分问题 想想看是不是和上面查找某个值的思路很相似啊

我们首先找到中间值

如果这个值大于我们的key值 我们的右边就不要了
如果这个值小于我们的key值 我们的左边就不要了

并且确认它符合条件之后将这个index值记录下来 最后返回用

（我们下面就直接打印index的位置 方便大家理解整个过程）

最后结束的时候 我们直接返回最后记录的一个index位置就好啦

代码表示如下

int main()
{
	int arr[] = { 1,1,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,7,8,9,12,13,14,16 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 0;
	int index = 0;
	cin >> k;
	// 设置左右下标
	int left = 0;
	int right = sz - 1;
	// 循环二分查找
	int mid = 0;
	while (left <= right)
	{
		// mid = (left + right) /2  防止溢出 
		mid = left + (right - left) / 2;
		// 判断是否是否等于我们要找的值
		if (arr[mid]>k)
		{
			index = mid;
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	cout << endl;
	cout << "找到了 下标位置是：" << index << endl;
	cout << "值是：" << arr[index] << endl;

	return 0;
}
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
27
28
29
30
31
32
33

整体表示如下

3. 在有序数组中找到小于某个数的位置

思路相似 改变一下大于小于号还有记录index的情况就可以了

代码表示如下

int main()
{
	int arr[] = { 1,1,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,7,8,9,12,13,14,16 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 0;
	int index = 0;
	cin >> k;
	// 设置左右下标
	int left = 0;
	int right = sz - 1;
	// 循环二分查找
	int mid = 0;
	while (left <= right)
	{
		// mid = (left + right) /2  防止溢出 
		mid = left + (right - left) / 2;
		// 判断是否是否等于我们要找的值
		if (arr[mid] >= k)
		{
			
			right = mid - 1;
		}
		else
		{
			index = mid;
			left = mid + 1;
		}
	}
	cout << endl;
	cout << "找到了 下标位置是：" << index << endl;
	cout << "值是：" << arr[index] << endl;

	return 0;
}
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
27
28
29
30
31
32
33
34

运行结果如下

4. 无序数组中寻找一个局部最小值

给你一个无序数组 要求你找到以一个局部最小值

这里的思路用的也是二分法

具体是什么思路呢？

我们来看

我们先比较最前的一个数和后面一个数 如果最前面的一个数小于它后面的一个数 是不是它就是一个局部最小值啊

如果比较了最前面的数和它的后一个数之后发现 它不是一个局部最小值 我们就比较最后面的数和最后面

的数的前面一个数

如果说最后面的数比它前面的一个数要小 那么是不是我们就能够找到最后面一个数是局部最小值啊

如果说上面的两次判断都不满足

那么我们的数组是不是就是一个这样子的状态

那么不管它怎么连 是不是一定会出现一个局部最小值啊

我们还是一样 从中间开始找

假设mid是这个样子的 那么我们是不是可以排除掉右边的一半区域了啊

之后我们继续找左边的二分 是不是继续重复这个步骤啊

代码表示如下

int main()
{
	int arr[] = { 3,1,5,6,7,5,7,8,1,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);

	int left = 0;
	int right = sz - 1;
	int mid = 0;
	int index = 0;
	
	// 判断首元素是不是局部最小值 
	if (arr[left] <= arr[left + 1])
	{
		index = left;
		
	}
	// 判断尾元素是不是局部最小值
	else if (arr[right] <= arr[right - 1])
	{
		index = right;
		goto End;
	}
	// 循环开始 	
	while (left<=right)
	{
		// 这里以及找过了首尾都不是局部最小值 开始二分
		mid = left + (right - left) / 2;
		if (arr[mid]<=arr[mid-1])
		{
			if (arr[mid] <= arr[mid + 1])
			{
				index = mid;
				break;
			}
			else
			{
				left = mid + 1;
			}
		}
		else 
		{
			right = mid - 1;
		}

	}


End:
	cout << "找到了 下标位置是：" << index << endl;
	cout << "值是：" << arr[index] << endl;

}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

我们只要重复这样简单的循环就能够找到局部最小值啦

演示结果如下

总结

本来想这期给大家带来二分法还有异或的介绍的 但是由于时间的限制只能先写这么多啦
这里给大家简单介绍了下 二分法的几个引用场景
由于博主能力有限 所以难免会出现一些纰漏 希望大佬们看到之后能够指正
阿尼亚 哇库哇库！