轻松拿捏C语言——二分查找

爆更小哇 2024-06-18 14:05:11 阅读 79

🥰欢迎关注 轻松拿捏C语言系列，来和小哇一起进步！✊

🌈感谢大家的阅读、点赞、收藏和关注💕

目录🎉

一、介绍🌈

二、步骤🌙

三、代码☀️

一、介绍

二分查找是一种在有序数组中查找某一特定元素的搜索算法。

举个生活中的例子，当我们要去图书馆借书时，知道了要找的图书编号，我们可以在一个大致范围的中间查找，然后在决定往前找还是往后找。这样就能比一本一本地找更加快速。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二、步骤

确定搜索范围，即数组的下标范围left和right。计算中间元素的下标mid = (left + right) / 2(注意整数除法）。

但是像这样求平均值，如果数字太大了超过int类型能表示的最大范围，这种算法就会有问题，整数会溢出。

所以我们可以换一个思路，把两数的差值的一半加到另一个数字中：

mid = left + (right-left) /2

判断中间元素与目标值的大小关系。

如果相等，则返回中间元素的下标。如果目标值小于中间元素，则在左半部分继续搜索（ right = mid - 1）。如果目标值大于中间元素，则在右半部分继续搜索（ left = mid + 1）。如果搜索范围 left大于 right，则表示数组中没有目标值，返回-1或其他表示未找到的值。

三、代码

法一：用递归实现

#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 在数组中的下标为 %d\n", key, ret); } else { printf("元素 %d 不在数组中\n",key); } return 0; }

法二：用循环实现

#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 在数组中的下标为 %d\n", key, ret); } else { printf("元素 %d 不在数组中\n",key); } return 0; }

使用循环的方式来实现二分查找，更直观且易于理解。

不过，递归的方式在某些情况下可能更简洁。

无论使用哪种方式，都需要确保数组是有序的，因为二分查找的前提是有序数组。