一、介绍
二分查找是一种在有序数组中查找某一特定元素的搜索算法。
举个生活中的例子，当我们要去图书馆借书时，知道了要找的图书编号，我们可以在一个大致范围的中间查找，然后在决定往前找还是往后找。这样就能比一本一本地找更加快速。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二、步骤
- 确定搜索范围，即数组的下标范围left和right。
- 计算中间元素的下标mid = (left right) / 2(注意整数除法）。
但是像这样求平均值，如果数字太大了超过int类型能表示的最大范围，这种算法就会有问题，整数会溢出。 所以我们可以换一个思路，把两数的差值的一半 加到另一个数字中： mid = left (right-left) /2
- 判断中间元素与目标值的大小关系。
- 如果相等，则返回中间元素的下标。
- 如果目标值小于中间元素，则在左半部分继续搜索（
right = mid - 1）。 - 如果目标值大于中间元素，则在右半部分继续搜索（
left = mid 1）。 - 如果搜索范围
left大于right，则表示数组中没有目标值，返回-1或其他表示未找到的值。
三、代码
法一：用递归实现
代码语言：javascript复制#include <stdio.h>
int Sort(int arr[], int left, int right, int Key) {
if (left > right)
return -1; // 搜索范围无效
int mid = left (right - left) / 2; //这种写法可避免溢出
if (arr[mid] == Key)
{
return mid; // 找到目标，返回下标
}
else if (arr[mid] > Key)
{
return Sort(arr, left, mid - 1, Key); // 在左半部分继续搜索
}
else
{
return Sort(arr, mid 1, right, Key); // 在右半部分继续搜索
}
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int key = 5;
int n = sizeof(arr) / sizeof(arr[0]);
int ret = Sort(arr, 0, n - 1, key);
if (ret != -1)
{
printf("元素 %d 在数组中的下标为 %dn", key, ret);
}
else
{
printf("元素 %d 不在数组中n",key);
}
return 0;
}法二：用循环实现
代码语言：javascript复制#include <stdio.h>
int Sort(int arr[], int N, int Key)
{
int left = 0;
int right = N - 1;
while (left <= right)
{
int mid = left (right - left) / 2;
if (arr[mid] == Key)
{
return mid;
}
else if (arr[mid] > Key)
{
right = mid - 1;
}
else
{
left = mid 1;
}
}
return -1; // 未找到目标值
}
int main()
{
int arr[] = {1, 3, 5, 7, 9};
int key = 5;
int n = sizeof(arr) / sizeof(arr[0]);
int ret = Sort(arr, n, key);
if (ret != -1)
{
printf("元素 %d 在数组中的下标为 %dn", key, ret);
}
else
{
printf("元素 %d 不在数组中n",key);
}
return 0;
}使用循环的方式来实现二分查找，更直观且易于理解。
不过，递归的方式在某些情况下可能更简洁。
无论使用哪种方式，都需要确保数组是有序的，因为二分查找的前提是有序数组。
