C语言 — — 二分查找初入门

C语言 — — 二分查找初入门

​
C语言中含有许许多多的算法，二分查找算是一个很经典的算法了

继上篇文章”初始C语言 – – 循环”后，我们大概了解了下C语言的循环，而今天，我们来学习一个借用循环来实现的小小算法。

传送门：初始C语言 – – 循环

二分算法的核心思想就是切半，然后借用左下标和右下标来控制范围。
先来讲讲流程：二分查找就是找到一个数组的下标以及最后一个下标，然后相加，再除2
将结果定义为mid，然后根据mid 来比较一下我们所需要查找的数，根据大小再继续循环这个操作，直到找到我们所需要的。
二分查找有个限制，就是数组里的东西需要从小到大/从大到小排列（至少你所需要查找的内容是这样的）需要有序数组（好像无序数组也可以，但我还没学到=.=）

我们来看看一个小例子：

我们定义了一个数组，存储了1-10 10个整形数据

这里我们定义了一个 left 一个 right ，还有我们需要查找的数，这里定义为k 并且k = 7
left 用来表示下标的第一个， right 表示最后一个数据的下标
这里，我们可以使用

int sz = sizeof(arr) / sizeof(arr[0]);

来计算最后一个下标的位置。这里的代码sizeof(arr) 表示的是这个数组的大小，而除以sizeof(arr[0]) 单个数据 就可以计算出这个数组的长度了。
假设我要寻找7这个数字，那么：
我们先使用公式 mid = (right + left) / 2 来表示中间数据的下标位置。

left是1 而right是10-1 = 9. mid取（left + right）/ 2 = 4

然后我们对比下，4这个下标对应的是5，而7在5的后面，也就是 Mid < n

那么，我们就拿掉下标4以及之前所有的数字，将left变成mid +1 也就是下标5（数字6）
那么这个时候，left = 5，right = 9
我们继续循环，（right + left）/ 2 = 14/2 = 7

我们需要7，但是mid是8 mid > n.
然后，我们可以将mid之后的全部清掉，right取mid-1 也就是下标6（数字7）
这个时候，left = 5，right = 6

我们继续循环使用公式（right + left）/ 2 = （5 + 6）/ 2 = 5

下标是5，那么根据上面的式子
mid = 5（数字6） 而我们需要查找的是7
所以我们继续使用公式（right + left） / 2 = （6 + 7）/ 2 = 6
这个时候，下标是6 也就是我们的数字7了

根据上面的推论，我们不难得出几个重要的式子：
当 mid < n
left = mid +1
当 mid > n
Right = mid – 1
Right +left = mid
那么，我们就能够使用循环来写出这个了
while（Left <= n）
If （mid < n )
Left = mid + 1;
Else if (mid > n)
Right = mid – 1;
Else
Printf(“找到了，是…”);

If (left > right)
Printf(”没找到”);

详细代码：

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 - left) / 2;if(arr[mid] < k)left = mid + 1;else if (arr[mid] > k)right = mid - 1;else {printf("Find it!,xiabiao = %d\n", mid);break;}}if (left > right)printf("Not found.\n");

以上就是本次的内容，因为我也是初学者QwQ，所以讲的不是很好，如果有什么错误希望可以有大佬指出！！感谢大家的观看！！！！