線性查找
public class SeqSearch {
public static void main(String[] args) {
int[] arr = {1, 9, 11, -1, 34, 89};
int index = serSearch(arr, 11);
if (index == -1) {
System.out.println("沒有找到該值");
} else {
System.out.println("找到,下標為: " + index);
}
}
/**
* 線性查找,找到一個滿足條件的值就回傳
*/
public static int serSearch(int[] arr, int value) {
// 線性查找是逐一對比,發現有相同的值,就回傳下標
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}
}
二分查找
二分查找是一種查詢效率非常高的查找演算法，又稱折半查找，
演算法思想： 對有序的序列，每次都是以序列的中間位置的數來與待查找的關鍵字進行比較，每次縮小一半的查找范圍，直到匹配成功，
注意: 使用二分查找的前提是資料是有序的，
查值索引的計算公式為： mid = (low + high) / 2
遞回實作二分查找
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 8, 10, 89, 1000, 1234};
int index = binarySearch(arr, 0, arr.length - 1, 1234);
System.out.println("查找到的下標為: " + (index == -1 ? "沒有找到該資料" : index));
}
/**
* 二分查找
*
* @param arr 陣列
* @param left 左邊的索引
* @param right 右邊的索引
* @param findVal 要查找的值
* @return 如果找到就回傳下標, 否則回傳-1
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
// 當left > right 說明遞回了整個陣列,但是沒有找到
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) {
// 向右遞回
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
// 向左遞回
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
}
非遞回實作二分查找
public class BinarySearchNoRecur {
public static void main(String[] args) {
int[] arr = {1, 3, 8, 10, 11, 67, 100};
int index = binarySearch(arr, 67);
System.out.println(index);
}
/**
* @param arr 待查找的陣列, arr是升序排序
* @param target 要查找的數
*/
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
// 向左邊查找
right = mid - 1;
} else {
// 向右邊查找
left = mid + 1;
}
}
return -1;
}
}
插值查找
基于二分查找演算法，將查找點的選擇改進為自適應選擇，可以提高查找效率，插值查找也屬于有序查找，
注： 對于表長較大，而關鍵字分布又比較均勻的查找表來說，插值查找演算法的平均性能比折半查找要好的多，反之，陣列中如果分布非常不均勻，那么插值查找未必是很合適的選擇，
插值索引的計算公式為： int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
代碼示例：
public class InsertValueSearch {
public static void main(String[] args) {
int[] arr = new int[100];
for (int i = 0; i < arr.length; i++) {
arr[i] = i + 1;
}
System.out.println(Arrays.toString(arr));
insertValueSearch(arr, 0, arr.length - 1, 66);
}
/**
* 插值查找
*
* @param arr 陣列
* @param left 左邊索引
* @param right 右邊索引
* @param findVal 要查找的值
* @return 找到回傳下標, 沒有找到回傳-1
*/
public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return -1;
}
// 求出mid
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if (findVal > midVal) {
// 說明應該向右邊遞回查找
return insertValueSearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
// 說明應該向左邊遞回查找
return insertValueSearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
}
斐波那契(黃金分割法)查找
由于博主暫時沒能理解透徹，就不誤導大家了，感興趣的話可以自己查找，示例代碼如下：
public class FibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
int[] arr = {1, 8, 10, 89, 1000, 1234};
System.out.println(fibSearch(arr, 89));
}
/**
* 因為后面 mid = low + F(k - 1) - 1,
* 需要使用到斐波那契數列,因此需要先獲取到一個斐波那契數列
* 非遞回方法得到一個斐波那契數列
*
* @return
*/
public static int[] fib() {
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < maxSize; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
/**
* 斐波那契查找演算法
* 使用非遞回的方式
*
* @param a 陣列
* @param key 需要查找的關鍵碼(值)
* @return 回傳對應的下標, 沒有回傳-1
*/
public static int fibSearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
// k表示斐波那契分割數值的下標
int k = 0;
// 存放mid值
int mid = 0;
// 獲取到斐波那契數列
int f[] = fib();
// 獲取到斐波那契分割數值的下標
while (high > f[k] - 1) {
k++;
}
// 因為 f[k] 值 可能大于 a 的長度,因此需要使用Arrays類,構造一個新的陣列,并指向temp[]
// 不足的部分會使用0填充
int[] temp = Arrays.copyOf(a, f[k]);
// 需要使用a陣列最后的數填充temp
for (int i = high + 1; i < temp.length; i++) {
temp[i] = a[high];
}
// 使用while回圈來處理,找到key
while (low <= high) {
// 只要這個條件滿足,就可以找
mid = low + f[k - 1] - 1;
if (key < temp[mid]) {
// 說明我們應該繼續向陣列的前面查找(左邊)
high = mid - 1;
/*
1. 全部元素 = 前面的元素 + 后邊的元素
2. f[k] = f[k - 1] + f[k - 2]
因為前面有f[k - 1]個元素,所以可以繼續拆分 f[k - 1] = f[k - 2] + f[k - 3]
即在 f[k - 1] 的前面繼續查找 k--
下次回圈的時候, mid = f[k-1-1]-1
*/
k--;
} else if (key > temp[mid]) {
// 向后面查找(右邊)
low = mid + 1;
/*
1. 全部元素 = 前面的元素 + 后邊的元素
2. f[k] = f[k - 1] + f[k - 2]
3. 因為后面有 f[k - 2], 所以可以繼續拆分 f[k - 1] = f[k - 3] + f[k - 4]
4. 即在 f[k - 2] 的前面進行查找 k-=2
即下次回圈 mid = f[k - 1 - 2] - 1
*/
k -= 2;
} else {
// 找到了,需要確定回傳的是哪個下標
if (mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}
如果覺得對你有幫助，歡迎來訪我的博客：http://jianjieming.com
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117870.html
標籤：其他
上一篇：應該如何刷 LeetCode？
下一篇：ID3演算法