二分查找法只适用于顺序存储,而且只适用于有序序列。
顺序存储是指用一段地址连续的存储单元存储相邻数据元素,比如我们常用的数组。这是一个物理上的概念。和它相对的是链式存储。
有序序列是指一个序列中的所有元素已经按照某种确定的方式排好了序,比如最简单的 int 数组的由小到大(或由大到小)。这是一个逻辑上的概念。
二分查找法指的是在有序的序列中查找某一元素,利用该序列已经有序的特点,每次比较范围中间的元素与目标元素的大小,即可确定目标值在中间值的前面还是后面,这样每次比较都能把查找范围缩小一半,达到快速查找的目的。
很显然,适用二分查找法的序列要满足两个条件:一是该序列内的元素是有序排列的(这很显然);二是该序列能够让程序直接访问它范围中间的元素,也就是需要能够随机存取。
我们知道链式存储是不支持随机存取的,比如一个单链表,我们想访问其中的第几个元素,就得从头结点开始一个一个往后查找,这种情况下非要用二分查找法实在是逆大天。
上面看完如果还是不太理解的话,我们可以具体分析一下:
二分查找本身是 T(logN)
对于顺序存储,随机存取是 T(1),不管你多长,给个下标我就飞过去了。那么顺序存储二分查找法的时间复杂度就是 O(logN)。
对于单链表,访问中间元素就得从头开始,把前面一半的结点都走一遍,T(N/2)。那么单链表二分查找法的时间复杂度就达到了 O(NlogN),要知道最简单的直接查找也就 O(N) 。
那么双向链表呢?也没有好到哪去,双向链表做二分查找法的时间复杂度也是 O(N),在某些情况下会比直接查找快一些,但仅此而已了。
至于二叉树等结构,由于已经不属于线性存储结构,这里就不讨论。