查找算法(折半查找，二叉排序樹，哈希表/散列查找)

折半查找

1. 把low放在最左邊，high放最右邊，mid=(high+low)/2
2. 如果low<=high則循環，當待查找數<mid，則high=mid-1，當待查數>mid，則low+1

3. 當low=mid的時候，該值與查找數相等，則輸出，否則當循環結束後仍未找到則break

   時間複雜度O(log2n)，比較次數<=樹的深度=log2n

   順序儲存有序表

分塊查找

• 塊間有序，塊内無序
• 是以塊間可以用折半查找法确定在哪一個塊，再用順序查找一個個看在塊中哪個位置

二叉排序樹

• if左子樹不空，則左子樹均小于根結點，if右子樹不空，則右子樹均大于根結點。具有遞歸性質，中序周遊則可得有序序列。

  

• 二叉排序樹的建立和插入都是按照上面查找的原則。新插入的結點一定的新的葉子結點
• 建立二叉排序樹時間複雜度為O(nlog2n)，插入一個的時間複雜度為O(log2n)
• 删除:删去葉子節點無影響; 隻有左子樹或右子樹，用左孩或右孩填補; 若左右都不為空，則找直接前驅或直接後繼補。

  

  散清單(哈希表)
• 思想: 通過對元素關鍵字的運算，直接求出元素的位址
• 散列函數兩個原則: 函數簡單，每個關鍵字隻有一個對應; 分布均勻，少沖突
• 構造位址函數方法:

1. 數學分析法: 取中間幾位亂序的數 ，或加減乘除等作為位址(首先要知道每一位數的分布情況)
2. 平方取中法: 先把編碼平方後，取中間的幾位數
3. 折疊法: 按n個數為間隔隔開，再加起來。

4. 除留餘數法: 選擇适當的p值(一般選小于表長的最大質數)，對關鍵字取餘(最好)

   以上方法可以自由組合

• 處理沖突方法

1. 開放位址法: H=(H(key)+d)%表長。d可以以線性序列(1，2，3…表長-1)，可以是二次探測(1²，-1²，2²，-2²…(表長/2)²)，也可以是随機數。隻要發生沖突的位址，則進行下一次探測
2. 鍊位址法: 把相同位址的記錄放在同一個單連結清單中。該适用于表長不确定的情況