数据结构与算法 - 二分查找

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

数据结构与算法 - 二分查找

前面介绍了插入排序、选择排序、快排等几种排序算法，后面会用几篇文章介绍几种查找算法，之所以要先介绍排序算法，再介绍查找算法，是因为要进行查找的数据都是已经排好序的，这是因为对于很多查找算法要求数据是有序的。这里将会介绍几种非常高效的算法：二分查找、红黑树、散列表、跳表。

下面介绍二分查找，二分查找也叫折半查找，相信大家都玩过或者见过猜数字游戏，由 A 向知道正确数字的 B 报出一个数字，B 告诉 A 所报数字是大于/小于所猜数字，然后继续进行猜测，直到猜到正确数字，如果希望最快的速度猜出数字，就需要每次报中间值。这就是二分思想的一种应用：将所要查找的数字与中间数进行比较，如果大于中间数，则用同样的方法在后半部分查找，如果小于，则用同样方法在前半部分查找。

用递归式表示二分查找如下：

转换成代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function BinarySearch(n,low,high,target)
  
  -- 最终也没有找到
  if low > high then
    return -1
  end
  
  -- 中间位置
  local mid = (low+high) // 2
  
  if n[mid] == target then
    return mid
  elseif n[mid] > target then
    return BinarySearch(n,low,mid-1,target)
  else
    return BinarySearch(n,mid+1,high,target)
  end
end

非递归形式代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function BinarySearchNoRecu(n,target)
    -- low,high 初始化
    local low,high = 1,#n

    while(low <= high) do
      local mid = (low + high) // 2
      if n[mid] == target then
        return mid
      elseif n[mid] > target then
        high = mid - 1
      else
        low = mid + 1
      end
    end

    -- 最终没有找到
    return -1
end

虽然上面代码是正确的，但是在某些情况可能得不到想要的结果，比如下面数组中，我们希望找到第一个等于6的值。

如果使用上面算法进行查找的话，返回值为3，并不是我们期望的第一个满足条件的值，那么该如何修改上面算法呢。我们可以这么考虑该问题，既然第二个6不是查找目标，那么它和其他不满足条件的元素一样，需要继续执行递归查找，那么此时查找条件就不能是简单的相等了，还需要是第一个相等的值，翻译成代码就是：

1
n[mid-1] ~= target

注意上面使用了mid-1，因此就需要边界下溢问题，当 mid = 0时，n[mid] 为第一个元素，因此也是满足条件的，最终代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function BinarySearchFirst(n,low,high,target)
  
  -- 最终也没有找到
  if low > high then
    return -1
  end
  
  -- 中间位置
  local mid = (low+high) // 2
  
  if n[mid] == target then
    -- 需要额外的条件
    if mid == 0 or n[mid-1] ~= target then
      return mid
    else
      -- 这里是查找第一个满足条件，因此需要继续在前半段进行查找，如果是查找
      -- 最后一个满足条件的，则需要在后半段进行查找
      return BinarySearchFirst(n,low,mid-1,target)
    end
  elseif n[mid] > target then
    return BinarySearchFirst(n,low,mid-1,target)
  else
    return BinarySearchFirst(n,mid+1,high,target)
  end
end

其他类似的问题，实现思路和上面是类似的：

  • 查找最后一个满足条件的元素
  • 查找第一个大于等于目标的元素
  • 查找最后一个小于等于目标的元素

二分查找性能

那么二分查找的时间复杂度是多少呢？每次查找都会讲数据规模进行折半，那么最坏的情况是，没有找到满足条件的元素，此时数据规模为0。

经过 k 次查找，数据规模的变化如下：

最后一次查找的数据规模为：$\frac{n}{2^k}$，此时值等于1，因为下一次数据规模为0就停止了查找，所以可以计算出 k 的值。

而单次查找的时间复杂度为$O(1)$，因此二分查找的时间复杂度为：$O(1)\log{n}=O(\log{n})$

也可以采用之前介绍的主方法来计算时间复杂度，首先将递归式换种写法：

  1. 根据二分查找的定义可以知道，a = 1,b = 2,f(n)=1
  2. 然后比较f(n)=1，和 $n^{\log_b^a}$=$n^0$=1 的渐进大小，两者的渐进值相同，满足主定理的第二种情况，因此时间复杂度为:$T(n)=O(n)=n^{\log_b^a}\log{n}$=$\log{n}$

对数是一个效率非常恐怖的数量级，比如从$2^32$(约42亿)个元素中查找某元素，最多只需要进行32次比较。

二分查找的局限

  1. 二分查找的数据必须是有序的。
  2. 二分查找依赖于数组的随机访问，如果采用其他顺序列表进行存储，则需要先根据位置，找到相应的中间元素，这样就完全失去了二分查找的意义，时间复杂度也会变大。
  3. 由于二分查找依赖于数组，而数组又是连续的内存结构，因此不太适用于数据规模太大的查找。