查找
查找
查找的定義
查找是一種根據給定的某個值在查找表中确定一個其關鍵字等于給定值的記錄的操作
順序查找
線性查找
線性查找是最基本的查找技術，從表頭或表尾開始逐個記錄與給定值比較，如果記錄關鍵字和給定值相等則查找成功，如果直到最後一個記錄都沒有相等則查找失敗
有序查找
折半查找
折半查找是一種有序查找，在有序表中取中間記錄作為比較對象，如果給定值與中間記錄的關鍵字相等則查找成功，如果過給定值小于中間記錄的關鍵字則在中間記錄的左半區繼續查找，如果過給定值大于中間記錄的關鍵字則在中間記錄的右半區繼續查找，不斷重複這個過程，如果記錄關鍵字和給定值相等則查找成功，如果直到最後一個記錄都沒有相等則查找失敗
插值查找
插值查找是一種改進的折半查找，折半查找每次都是取中間記錄作為比較對象，而插值查找每次是取插值記錄作為比較對象，折半查找的插值固定為 1 / 2 ，而插值查找的插值為給定關鍵字與最小記錄關鍵字之差比上最大記錄關鍵字與最小記錄關鍵字之差
斐波那契查找
斐波那契查找是一種改進的折半查找，折半查找每次都是取中間記錄作為比較對象，而斐波那契查找每次是取斐波那契數列記錄作為比較對象，斐波那契數列記錄的計算和有序表記錄數量在斐波那契數列中所處的位置相關
線性索引
稠密索引
稠密索引的索引表中，每個索引項都是唯一的關鍵字記錄，索引項排列有序
分塊索引
分塊索引的索引表中，每個索引項都是唯一的關鍵字記錄塊，關鍵字記錄塊需要滿足塊内無序塊間有序，索引項排列有序
反向索引
反向索引的索引表中，每個索引項都是唯一的次關鍵字記錄，索引項排列有序
二叉查找樹
二叉查找樹
二叉查找樹是一種二叉樹，左子樹上所有結點的值均小于根結點的值，右子樹上所有結點的值均大于根結點的值，并且左右子樹也均為二叉查找樹
平衡二叉樹
平衡二叉樹是一種二叉查找樹，每個結點的左子樹和右子樹的絕對高度差均不大于1
多路查找樹
多路查找樹
多路查找樹是一種樹，每個結點可以存儲多個元素，每個結點可以有多個孩子
多路查找樹的類型
2-3樹
2-3-4樹
B樹
B+樹
B樹
B樹是一種平衡的多路查找樹，2-3樹和2-3-4樹都是B樹的特例
B+樹
B+樹是一種B樹的變形樹，嚴格意義上來講已經不能算樹，因為B+樹的葉結點之間是有連線的，是為應對檔案系統所需而有的資料結構
哈希表查找
哈希表查找
哈希表查找是一種利用哈希函數在哈希表中查找記錄的技術
哈希函數的構造方法
直接定址法
數字分析法
平方取中法
折疊法
除留餘數法
随機數法
哈希沖突的處理方法
開放定址法
再哈希函數法
鍊位址法
公共溢出區法
排序
排序
排序的定義
排序是一種使任意序列成為一個按照關鍵字有序的序列的操作
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)