二分查找(上)

Tuesday, April 23, 2019

二分查找基本思想

比如我们要猜数字,随机写一个0-99以内的数字,几次能快速猜到,假如写的是23。

file

假如我们有10个订单,利用二分思想查一个金额为19的订单出来

file

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

二分查找的时间复杂度为O(logn),某些情况下,比O(1)的算法还要高效。

简单的二分查找算法实现

<code class="language-swift">public func bsearch(_ array: [Int], n: Int, value: Int) -> Int {
    var low = 0
    var high = n - 1

    while low <= high {
        int mid = (low + high) / 2
        if a[mid] == value {
            return mid
        }else if  a[mid] < value {
            low = mid + 1
        }else {
            high = mid - 1
        }
    }
    return -1
}</code>

有几个要注意的地方

  • 注意是 low <= high 不是 low < high
  • mid的取值,如果high和low过大,有可能会溢出,写成 low + (high - low) / 2
  • low和high的更新要+1和-1,否则可能会进入死循环

二分查找局限性

  • 二分查找依赖顺序结构,简单来说就是数组
  • 二分查找针对的是有序数据
  • 数据量太小不适合二分查找
  • 数据量太大也不适合二分查找
数据结构-算法

二分查找(下)

排序优化