假定一張表包含N個記錄，K為待查找之記錄的關鍵字。對半查找的基本思想是，首先將K與表中間的記錄的關鍵字K（n/2）進行比較，其結果由三種情況，K<K(n/2),K>K(n/2),K=K(n/2).若查找不成功，則根據比較結果確定下一次應該到表的哪一半去查找，並對確定了的這一半重複上述過程。如此下去或查找成功，或直到表的長度為0.在至多進行了int(㏒2 N)+1 次比較之後，或者找到這個關鍵字，或者確定它不存在。
基本介紹
- 中文名：對半查找
- 外文名：Binary search
定義,性質,套用,
定義
假定一張表包含N個記錄，K為待查找之記錄的關鍵字。對半查找的基本思想是，首先將K與表中間的記錄的關鍵字K（n/2）進行比較，其結果由三種情況，K<K(n/2),K>K(n/2),K=K(n/2).若查找不成功，則根據比較結果確定下一次應該到表的哪一半去查找，並對確定了的這一半重複上述過程。如此下去或查找成功，或直到表的長度為0.在至多進行了㏒2 N 次比較之後，或者找到這個關鍵字，或者確定它不存在。
性質
對半查找可以在基於關鍵字比較的查找中極大的提高順序查找的效率。
套用
一致對半查找等套用。
