二元搜索(Binary Search)算法又称为二分搜索(Half-Interval Search)算法或是对数搜索(Logarithmic Search)算法,顾名思义,这套算法的核心思想就在于「二分」,可以在已排序好的串行中进行高效率的搜索。

二元搜索法(Binary Search)

二元搜索法的概念

相对于先前介绍过的线性搜索法,二元搜索法不需要把集合中的元素一个一个拿出来判断,因为它所搜索的集合必须是已经排序好的串行,所以可以直接利用元素的大小来决定下次要寻找的位置。

在一个已排序好的串行中搜索元素是一件轻松容易的事情,我们可以先设置搜索范围,每次都用这范围最中间的元素来与要查找的目标元素比大小,如果要查找的目标元素比较大,表示如果目标元素存在于该串行中的话,其一定是位在目前范围的后半段(值大的那段);反之,如果要查找的目标元素比较小,表示如果目标元素存在于该串行中的话,其一定是位在目前范围的前半段(值小的那段)。在下次搜索的时候,也是一样拿目标元素与前半段或是后半段的正中央元素进行比较,如此反复动作,直到找出相同的元素为止;或者直到查找范围内已经没有任何元素时,表示要找的元素并不存在于串行中。

二元搜索法的过程

假设现在有个已排序好的整数数组,内容如下:

索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81

然后我们要用二元搜索法来找到元素 69。这边可以看到此数组的长度为 10,是偶数,所以并不能刚好选到正中间的元素,不过这也没关系,选择索引 4 或是索引 5 都可以,在此以索引 4 为例。

       ●              ○                  ●
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                     69 > 38

由于我们要找的元素 69 比索引 4 的元素值 38 还要来得大,因此可以知道若元素值 69 存在于该数组的话,那么它一定是在索引值大于 4 的位置,索引值小于 4 的元素们就都不用去管了。所以下一次搜索,我们要选择索引 5 到索引 9 的中间元素,也就是索引 7。

                           ●      ○      ●
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                                69 == 69

如此一来就找到元素 69 了,其存在于数组中的索引 7 的位置。如何?够快吧!

二元搜索的过程动画

二元搜索法的程序实作

在实作程序的时候,应该要避免使用递归(Recursive)的结构,因为递归需要不断地重新建构函数的堆栈空间,硬件资源的负担会比较大,且若是递归层数过多还会导致堆栈溢出(Stack Overflow)。所以比较好的做法还是在一个函数内以循环迭代的方式来完成。

二元搜索法的复杂度

以 #{{n}}# 来表示要搜索的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(\log n)}}# 元素不在串行中,或者是二分到不能再分时才被发现。
最佳时间复杂度 #{{O(1)}}# 要查找的元素刚好位于串行的中间。
平均时间复杂度 #{{O(\log n)}}#
最差空间复杂度(递归) #{{O(\log n)}}#
最差空间复杂度(迭代) #{{O(1)}}#