算法和数据结构——搜索

搜索：从数据集合中找出目标元素

(当然是越快越好了)

基本的搜索算法有如下三种：

线性搜索、二分搜索、散列搜索。

线性搜索：从头到尾依次查找目标元素，已经找到则返回，效率低但可用于任何形式的数据。O(n)

二分搜索：作用于已排好序的数据集，将搜索目标指向之间，经过判断取其中的一边再搜索。(可以在极短时间内完成搜索) O( $\log_2 n$ )

散列搜索（利用哈希值）：利用关键(值)带入特定散列函数找其位置，效率极高。

线性搜索：

二分搜索：

散列搜索：

双散列函数：以h1(k)为基底若发生冲突，则以增加h2(k)个单位。

（i是冲突次数）

H(k) = h(k,i)

= ( h1(k) + i * h2(k) ) % m

（m为总基数）