查找在實(shí)際的應(yīng)用開(kāi)發(fā)中很常見(jiàn)，所以有必要詳細(xì)深入的梳理一下。根據(jù)查找過(guò)程時(shí)咽块，是否需要同時(shí)插入或刪除元素，可分為靜態(tài)查找和動(dòng)態(tài)查找欺税。
一侈沪、靜態(tài)查找
1.順序查找
順序查找又稱為線性查找，是一種最簡(jiǎn)單晚凿、最常用的查找方法亭罪。
/**
* 順序查找
* @param a 查找表
* @param x 查找關(guān)鍵字
* @return 關(guān)鍵字在查找表中的位置，未找到則返回-1
*/
public static int sequenceSearch(int a[], int x) {
if(a != null && a.length > 0) {
for (int i = 0; i < a.length; i++) {
if(a[i] == x) {
return i;
}
}
}
return -1;
}
下面說(shuō)說(shuō)順序查找算法的事件復(fù)雜度晃虫，如果查找成功皆撩，平均的遍歷次數(shù)為(n+1)/2；如果未找到哲银，則遍歷次數(shù)為n扛吞。順序查找的優(yōu)點(diǎn)就是算法簡(jiǎn)單、應(yīng)用廣泛荆责，并且對(duì)表的結(jié)構(gòu)沒(méi)有任何要求滥比；缺點(diǎn)就是查找效率較低，當(dāng)數(shù)據(jù)量較大時(shí)做院，不推薦使用順序查找盲泛。
2.二分查找
二分查找是一種很高效的方法濒持，但前提是需要查找表中的元素必須有序排列，如果要使用該方法寺滚，則需要先對(duì)查找表中的元素進(jìn)行排序柑营。
算法思路為，取表(元素按照升序排列)中間元素作為比較對(duì)象村视，如果給定值與中間元素相等官套，則查找成功；如果給定值比中間元素大蚁孔，則在中間元素右邊的區(qū)間繼續(xù)查找奶赔；如果給定值比中間元素小，則在中間元素左邊的區(qū)間繼續(xù)查找杠氢，以此類推站刑，具體的實(shí)現(xiàn)過(guò)程如下：
/**
* 二分查找算法
* @param a 查找表
* @param x 查找關(guān)鍵字
* @return 關(guān)鍵字在查找表中的位置，未找到則返回-1
*/
public static int binarySearch(int a[], int x) {
if(a != null && a.length > 0) {
int low = 0;
int high = a.length;
int mid = 0;
while (low < high) {
mid = (high + low)/2;
if(a[mid] == x) {
return mid;
}else if (a[mid] > x) {
high = mid - 1;
}else {
low = mid + 1;
}
}
}
return -1;
}
二分查找的效率較高鼻百，具體的時(shí)間復(fù)雜度為log2(n)绞旅，也就是說(shuō)8個(gè)元素中，只需要查找3次就可以知道結(jié)果(包括查找成功和未找到)愕宋。
3.斐波那契查找
需要介紹一下黃金分割比例玻靡，是指事物各部分之間存在著一定的數(shù)學(xué)關(guān)系结榄。將事物一分為二中贝，較大部分與較小部分之比等于整體與較大部分之比，比值為1:0.618或者1.618:1臼朗。
還需要介紹斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（從第三個(gè)數(shù)開(kāi)始邻寿，后邊每一個(gè)數(shù)都是前兩個(gè)數(shù)的和）。隨著斐波那契數(shù)列的遞增视哑，前后兩個(gè)數(shù)的比值會(huì)越來(lái)越接近0.618绣否，利用這個(gè)特性，我們就可以將黃金分割比例運(yùn)用到查找技術(shù)中挡毅。
斐波那契查找是在二分查找的基礎(chǔ)上進(jìn)行優(yōu)化蒜撮，查找表必須是有序排列。
算法思路：
4.插值查找
5.分塊查找
二跪呈、動(dòng)態(tài)查找
1.二叉排序樹(shù)
2.平衡二叉樹(shù)
