ASL
由于查找算法的主要運(yùn)算是關(guān)鍵字的比較，所以通常把查找過程中對(duì)關(guān)鍵字的平均比較次數(shù)(平均查找長度)作為衡量一個(gè)查找算法效率的標(biāo)準(zhǔn)惋增。ASL= ∑(n,i=1) Pi*Ci,其中n為元素個(gè)數(shù)叠殷，Pi是查找第i元素的概率改鲫，一般為Pi=1/n,Ci是找到第i個(gè)元素所需比較的次數(shù)。
順序查找
原理是讓關(guān)鍵字與隊(duì)列中的數(shù)從最后一個(gè)開始逐個(gè)比較，直到找出與給定關(guān)鍵字相同的數(shù)為止像棘，它的缺點(diǎn)是效率低下稽亏。 ** 時(shí)間復(fù)雜度為O(n) ** 。
折半查找
** 折半查找要求線性表是有序表** 缕题。搜索過程從數(shù)組的中間元素開始截歉，如果中間元素正好是要查找的元素，則搜索過程結(jié)束;如果某一特定元素大于或者小于中間元素烟零，則在數(shù)組大于或小于元素的那一半中查找瘪松，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空锨阿，則代表找不到宵睦。這種搜索算法每一次比較都使搜索范圍縮小一半。 ** 折半搜索每次把搜索區(qū)域減少一半墅诡，時(shí)間復(fù)雜度為O（logn） ** 壳嚎。
- 可以借助二叉判定樹求得折半查找的平均查找長度 ： log2 (n+1) - 1。
- 折半查找在失敗時(shí)所需比較的關(guān)鍵字個(gè)數(shù)超過判定樹的深度末早，n個(gè)元素的判定樹的深度和n個(gè)元素的完全二叉樹的深度相同 log2(n) + 1 烟馅。
public int binarySearchStandard(int[] num, int target){
int start = 0;
int end = num.length - 1;
while(start <= end){ //注意1
int mid = start + ((end - start) >> 1);
if(num[mid] == target)
return mid;
else if(num[mid] > target){
end = mid - 1; //注意2
}
else{
start = mid + 1; //注意3
}
}
return -1;
}
- 如果是start < end,那么當(dāng)targe等于num[num.length - 1],會(huì)找不到該值。
- 因?yàn)閚um[mid] > targe,所以如果有num[index] == target,index一定小于mid,能不能寫成end = mid呢然磷？ 舉例來說:num = {1,2,5,7,9};如果寫成end = mid郑趁，當(dāng)循環(huán)到start = 0,end = 0時(shí)(即num[start] = 1,num[end] = 1時(shí))，mid將永遠(yuǎn)等于0,此時(shí)end也將永遠(yuǎn)等于0样屠，陷入死循環(huán)穿撮。也就是說尋找targe = -2，程序?qū)⑦M(jìn)入死循環(huán)痪欲。
- 因?yàn)閚um[mid] < targe,所以如果有num[index] == targe,index一定大于mid,能不能寫成start = mid呢悦穿？舉例來說，num = {1,2,5,7,9};如果寫成start = mid,當(dāng)循環(huán)到start = 3,end = 4時(shí)(即num[start] = 7,num[end] = 9時(shí))业踢，mid將永遠(yuǎn)等于3,此時(shí)start也將永遠(yuǎn)等于3,陷入死循環(huán)栗柒。也就是說尋找target = 9時(shí)，程序?qū)⑦M(jìn)入死循環(huán)知举。
分塊查找
分塊查找又稱索引順序查找瞬沦，它是一種性能介于順序查找和折半查找之間的查找方法。 ** 分塊查找由于只要求索引表是有序的雇锡，對(duì)塊內(nèi)節(jié)點(diǎn)沒有排序要求逛钻，因此特別適合于節(jié)點(diǎn)動(dòng)態(tài)變化的情況。
