C语言中二分法的简单理解

2023-08-19 12:46| 来源: 网络整理| 查看: 265

二分法介绍

当我们想要在一个有序数组中查找某一个数据时，除了按顺序一个一个查找外，还可以通过二分法进行查找，特别是在含数据较多的数组中查找时，二分法的效率可能会更高。

所谓二分法，其实就是每一次拿要找的数和数组中间的数进行比较，举个例子，现在有1到10十个数，如果要查找的数是7，那么二分法会先和5进行比较，因为7比5大，所以查找的范围就变成了6到10，直接排除了一半的数组，在以此类推，直到找到7为止。

编写过程中遇到的问题

在初次编写二分法程序的过程中，我发现了一个问题。

#include int main() { int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; printf("请输入1-10之间的整数："); int input = 0; scanf("%d", &input); int left = 0; int right = (sizeof(arr) / sizeof(int)) - 1; for (;;) { int mid = (left + right) / 2; if (input > arr[mid]) { left = mid; } else if (input < arr[mid]) { right = mid; } else { printf("找到了,是第%d个\n", mid + 1); break; } } return 0; }

但是在检验过程中发现，该方法是无法查找到数组中最大的数10的。检查了一遍发现，因为mid的类型是int，在进行最后一步查找时，left变成了8，right是9，(8+9)/2在int类型里等于8，所以永远不能找到最后一位数，改进之后：

#include int main() { int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; printf("请输入1-10之间的整数："); int input = 0; scanf("%d", &input); int left = 0; int right = (sizeof(arr) / sizeof(int)) - 1; for (;;) { int mid = (left + right) / 2; if (input > arr[mid]) { left = mid + 1; } else if (input < arr[mid]) { right = mid - 1; } else { printf("找到了,是第%d个\n", mid + 1); break; } } return 0; }

在原先的代码中，如果input > arr[mid]，那么就执行 left=mid ，拿1到10的例子说，left是等于mid等于(0+9)/2=4（注意这里4是下标），这样下一次查找的范围就是从5到10，而改进后变成left=mid+1; 则下一次查找范围变成了6到10，提高了效率，在查找10时，也变成了(9+9)/2=9; 不存在找不到最后一位的情况。

【本文地址】

C语言中二分法的简单理解

C语言中二分法的简单理解

今日新闻

推荐新闻