Loading... ## 前言: 假设要在电话簿中找一个名字以K开头的人,可以从头开始翻页,直到进入以K开头的部分。但是你可能不会这样做,你可能会从字典的中间开始找,因为你知道以K开头的名字在电话簿的中间。 这是一个查找问题,都可以使用同一种算法来解决问题,这种算法就叫二分法。 ## 查找效率: log以2为底n的对数 ## 要求: 仅当列表是有序的时候,二分法才管用。 ### 原理: while(最小值 <= 最大值) { ``` 查找的值与中间值比较(中间值 == (最小值 + 最大值)/2); ``` ``` 如果查找值等于中间值 - > 找到数据; ``` ``` 如果查找值小于中间值 -> 最大值 == 中间值 - 1; ``` ``` 如果查找值大于中间值 -> 最小值 == 中间值 + 1; ``` } ### 代码实现: ```cpp #include<stdio.h> int main() { int array[] = {11, 22, 33, 44, 55}; int temp; scanf("%d", &temp); int low = 0; int high = sizeof(array) / sizeof(array[0]) - 1; while(low <= high) { int mid = (low + high) / 2; if(temp == array[mid]) { return printf("%d存于数组中!", temp); } if(temp > array[mid]) { low = mid + 1; } else { high = mid - 1; } } return printf("%d不存于数组中!", temp); } ``` ### 中间值讨论: <div class="tip inlineBlock success"> 为了防止中间值溢出情况出现我们可以用: low + (high - low)/ 2 代替 (low + high)/ 2 </div> 最后修改:2021 年 08 月 30 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果文章有用,请随意打赏。