1.折半查找法是一种在有序数组中查找某一特定元素的搜索算法(若无序需先将其排序）
2.首先确定好左(left)、中(mid)、右(right)3个位置,一般情况下中间位置mid=(left+right)/2
但如果查找的范围非常庞大，left+right的数值会超过程序所承受的范围，导致数据的溢出泄露
这时我们可以采取平均划分的办法来进行运算，对其数值较大的一方减去最小的一方
得到他们之间所相差数，将相差数进行平均划分给2方，从而就可以得到相应的中间数
mid=left+(right-left)/2
3.方法步骤
(1)搜索过程中从中间开始查找，若中间元素刚好等于所要查找的数则查找结束
(2)若中间元素小于所要查找的元素，则查找元素存在于中间元素的右边,可将左侧数据进行排除，并重新确定left的位置，left则取新区间最左侧的位置，即：left=mid+1
(3)若中间元素大于所要查找的元素，则查找元素存在于中间元素的左边,可将右侧数据进行排除，并重新确定right的位置，left则取新区间最右侧的位置，既：right=mid-1
(4)若left>right,则数据中并没有所要查找的数据
4.优点：比较次数较少，查找速度快，平均性能好
缺点：查找数据必须在有序数组中才能进行，且插入删除困难
5.因此折半查找法适用于不经常变动而查找频繁的有序数组
6.代码实现
#include
void My_sort(int arr[],int sz) //对数组进行排序 { int i = 0; int j = 0; for (i = 0; i < sz - 1; i++) { for (j = 0; j < sz - i - 1; j++) { if (arr[j] > arr[j + 1]) { int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t; } } } } int My_lin(int arr[], int sz) { int r = 0; int left = 0; int right = sz-1; printf(" \n"); printf("请输入想要查找的数："); scanf("%d", &r); while(left
r) { right = mid - 1; } else { printf("查找成功："); return mid; } } if (left > right) { printf("查找失败,请重新输入："); return 0; } } int main() { int i = 0; int arr[] = { 1,3,5,7,9,2,4,6,8,10 }; int sz = sizeof(arr) / sizeof(arr[0]); My_sort(arr, sz); while(1) { // for (i = 0; i < sz; i++) //检查排序是否有问题 // { // printf("%d", arr[i]); // } int ret = My_lin(arr, sz); printf("下标=%d\n", ret); } return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/200345.html原文链接：https://javaforall.net
