查找
1. 二分查找
二分查找(折半查找)必須采用順序存儲(chǔ)結(jié)構(gòu)，并且必須按關(guān)鍵字大小有序排列蝗蛙。
二分查找求mid公式：
二分查找的時(shí)間復(fù)雜度：
遞歸實(shí)現(xiàn)二分查找-：
// 二分查找(遞歸)
public static int binarySearch(int[] container, int fromIndex, int toIndex, int key) {
if (fromIndex > toIndex)
// 沒找到，返回負(fù)數(shù)
return -(fromIndex + 1);
int mid = (fromIndex + toIndex) >> 1;
int midVal = container[mid];
if (midVal < key)
return binarySearch(container, mid + 1, toIndex, key);
else if (midVal > key)
return binarySearch(container, fromIndex, mid - 1, key);
else
// 找到了，返回索引
return mid;
}
非遞歸實(shí)現(xiàn)二分查找*：
// 二分查找(非遞歸)
public static int binarySearch(int[] container, int key) {
int low = 0;
int high = container.length - 1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = container[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
// 找到了，返回索引
return mid;
}
// 沒找到，返回負(fù)數(shù)
return -(low + 1);
}
2. 插值查找
插值查找基于二分查找盲泛，將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇，提高查找效率键耕。
插值查找求mid公式：
插值查找的時(shí)間復(fù)雜度：
當(dāng)關(guān)鍵字分布較均勻時(shí)，采用插值查找速度較快屈雄；否則村视，插值查找不一定比二分查找速度快。
插值查找代碼實(shí)現(xiàn)：修改二分查找的mid和判斷條件
// 插值查找(修改二分查找的mid和判斷條件)
public static int interpolationSearch(int[] container, int key) {
int low = 0;
int high = container.length - 1;
// key若不在[low, high]區(qū)間內(nèi)酒奶，則找不到蓖议，
// 而且也防止了因key過大或過小讥蟆，導(dǎo)致mid過大或過小勒虾，而造成數(shù)組越界
while (low <= high && container[low] <= key && key <= container[high]) {
int mid = low + (key - container[low]) / (container[high] - container[low]) * (high - low);
int midVal = container[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
// 找到了，返回索引
return mid;
}
// 沒找到瘸彤，返回負(fù)數(shù)
return -(low + 1);
}
3. 斐波那契查找
斐波那契搜索也是二分查找的一種提升算法修然，通過運(yùn)用黃金比例的概念在數(shù)列中選擇查找點(diǎn)進(jìn)行查找，提高查找效率愕宋。
黃金比例又稱黃金分割，是指將整體一分為二结榄，較大部分與較小部分之比等于整體與較大部分之比中贝，其比值約為1:0.618或1.618:1。
隨著斐波那契數(shù)列的遞增臼朗，前后兩個(gè)數(shù)的比值會(huì)越來(lái)越接近0.618邻寿；斐波那契數(shù)列如下：
由上面公式可知：只要順序表的長(zhǎng)度為，就可以將該順序表劃分成
三段绣否，但順序表的長(zhǎng)度可能小于
誊涯，因此需要將順序表的長(zhǎng)度增加至
。
斐波那契查找求mid公式：
斐波那契查找的時(shí)間復(fù)雜度：蒜撮；與折半查找相比，斐波那契查找的優(yōu)點(diǎn)是它只涉及加法和減法運(yùn)算段磨，而不用除法
斐波那契搜索是一種函數(shù)估值次數(shù)最少的最優(yōu)搜索方法
插值查找代碼實(shí)現(xiàn)：結(jié)合上面分析來(lái)理解
// 斐波那契查找
public static int fibonacciSearch(int[] container, int key) {
int low = 0;
int high = container.length - 1;
// 獲取一個(gè)斐波那契數(shù)列
List<Integer> fibonacci = getFibonacciSequence(container.length);
// n代表第幾個(gè)斐波那契數(shù)
int n = fibonacci.size() - 1;
// 將數(shù)組擴(kuò)容至F[n]-1
int[] expanded = Arrays.copyOf(container, fibonacci.get(n) - 1);
// 用原容器最后一個(gè)數(shù)來(lái)填充多出來(lái)的空間
for (int i = container.length; i < expanded.length; i++) {
expanded[i] = container[container.length - 1];
}
// 每一輪的搜索區(qū)間長(zhǎng)度為F[n]-1取逾，就可以分割
while (low <= high) {
int mid = low + (fibonacci.get(n - 1) - 1);
int midVal = expanded[mid];
if (midVal < key) {
low = mid + 1;
// 下一輪在右邊區(qū)域找，其長(zhǎng)度為F[n-2]-1苹支，因此讓n變成n-2
n -= 2;
} else if (midVal > key) {
high = mid - 1;
// 下一輪在左邊區(qū)域找菌赖，其長(zhǎng)度為F[n-1]-1沐序，因此讓n變成n-1
n -= 1;
} else {
// 如果找到的是原容器中的元素，直接返回索引
if (mid <= high)
return mid;
else
// 如果找到的是填充值堕绩，則返回原容器最后一個(gè)元素的索引
return high;
}
}
// 沒找到策幼，返回負(fù)數(shù)
return -1;
}
// 獲取一個(gè)斐波那契數(shù)列，有且僅有(最后一個(gè)斐波那契數(shù)-1)大于等于容器容量
private static List<Integer> getFibonacciSequence(int length) {
ArrayList<Integer> fibonacci = new ArrayList<>();
fibonacci.add(1);
fibonacci.add(1);
int last = 1;
while (fibonacci.get(last) - 1 < length) {
// 給斐波那契數(shù)列中添加一個(gè)數(shù)
fibonacci.add(fibonacci.get(last) + fibonacci.get(last - 1));
last++;
}
return fibonacci;
}
