二分查找（折半查找）法

我与梦想有个约会

发布于 2023-10-20 16:15:27

1990

发布于 2023-10-20 16:15:27

文章被收录于专栏：jiajia_deng

二分查找的前提是数据一定要有序，否则一切皆为空谈。通过有序的一段数据使用二分查找较常规遍历查找算法速度要快一些。其中二分查找发有两种实现，一种为常规while循环，另外一种为递归。具体的实现步骤如下：

假设集合中数据是升序排列，将集合中间的元素同目标比较。若相等，则查找成功。否则利用中间位置将集合分成两个子集。
若中间元素大于目标元素，则在左子集中查找，否则在右子集中查找。
重复以上操作，直至找到要查找的元素，或是直到子集不存在查找的数据。
以上内容来自“传智播客”讲师课件。

#include <stdio.h>
#include <stdlib.h>
int binarySearch(int *data, int low, int high, int find)
{
// 循环进行查找，终止条件为low==high下标或low > high下标
// 否则一直循环下去
while (low <= high)
{
// 每次进入循环都将下标除以2，结果始终为隐式转换后的int整形
int mid = (low + high) / 2;
// 判断除2后的下标所对应的数据是否就是我们找的数据
// 如果是则直接返回
if (data[mid] == find)
return mid;
// 否则判断该下标对应的数据是否大于查找的数据
else if (data[mid] > find)
// 如果大于则把高位下标指向到mid的左侧位置
high = mid - 1;
else
// 如果小于则把低位下标指向到mid的右侧位置
low = mid + 1;
// 依次循环
}
// 如果循环中没有找到需要的数据则返回-1
return -1;
}
int main(int argc, char* argv[])
{
int arr[] = { 102, 346, 478, 552, 621, 760, 896, 910 };
int find = binarySearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 478);
printf(“查找到下标为 %d 的值是我们需要的数据 %d：\n”, find, arr[find]);
system(“pause”);
return 0;
}
另外一种递归实现方式如下：
#include <stdio.h>
#include <stdlib.h>
int binarySearch(int* data, int low, int high, int find)
{
// 循环的终止条件，也就是递归的终止条件
if (low <= high)
{
int mid = (low + high) / 2;
if (find == data[mid])
return mid;
else if (find > data[mid])
binarySearch(data, mid + 1, high, find);
else
binarySearch(data, low, mid - 1, find);
}
else
{
return -1;
}
}
int main(int argc, char* argv[])
{
int arr[] = { 102, 346, 478, 552, 621, 760, 896, 910 };
int find = binarySearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 478);
printf(“查找到下标为 %d 的值是我们需要的数据 %d：\n”, find, arr[find]);
system(“pause”);
return 0;
}

下图是根据以上代码制作的二分查找法的示例图，可参考学习：