二分查找最坏查找次数_Go语言二分查找

作者：weixin_40725706 | 2024-05-26 01:20:11

踩

二分查找最坏情况下比较次数

什么是二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

时间复杂度分析

假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是除以 2，最坏情况下，直到查找被缩小为空才停止。

可以看出来，这是一个等比数列。其中 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。

代码实现

最简单的二分查找：就是在有序数组中不存在重复的元素。实现代码如下：


func bsearch(arr []int, n int, target int) int {
      low := 0  height := n - 1  for low <

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/624541