线性查找算法
从线性数列中
的起始位置依次比较
判断数列中是否包含需要查找的数
,若找到
了直接返回下标
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| public class SeqSearch {
public static void main(String[] args) { int[] arr = {1, 4, 7, 2, 3, 9}; int search = seqSearch(arr, 7); if (search == -1){ System.out.println("没有找到"); }else { System.out.println("找到了"); } }
public static int seqSearch(int[] arr, int value) { for (int i = 0; i < arr.length; i++) { if (arr[i] == value) { return i; } } return -1; } }
|
二分查找算法
查找的数组必须是有序的
思路
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
|
public class BinarySearch { public static void main(String[] args) { int[] arr = {1, 3, 7, 8, 10, 12, 14, 16, 27}; int search = binarySearch(arr, 0, arr.length - 1, 9); System.out.println(search);
}
public static int binarySearch(int[] arr, int left, int right, int findVal) { 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; } } }
|
上面代码存在问题,如果有重复数据,只会返回一个
优化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
|
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) { if (left > right) { return new ArrayList<>(); } int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { return binarySearch2(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return binarySearch2(arr, left, mid - 1, findVal); } else {
List<Integer> list = new ArrayList<>(); int temp = mid - 1; while (true) { if (temp < 0 || arr[temp] != findVal) { break; } list.add(temp); temp--; } list.add(mid);
temp = mid + 1; while (true) { if (temp > arr.length - 1 || arr[temp] != findVal) { break; } list.add(temp); temp++; } return list; }
}
|
插值查找算法
公式:int mid = left + (right -left) * (findVal - arr[left]) / (arr[right] - arr[left])
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
|
public class InsetValueSearch { public static void main(String[] args) { int[] arr = new int[20]; for (int i = 0; i < 20; i++) { arr[i] = i + 1; }
int search = insetValueSearch(arr, 0, arr.length - 1, 15); System.out.println(search);
}
public static int insetValueSearch(int[] arr, int left, int right, int findVal) { System.out.println("WWWWWW"); if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) { return -1; }
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]); int midVal = arr[mid];
if (findVal > midVal) { return insetValueSearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return insetValueSearch(arr, left, mid - 1, findVal); } else { return mid; }
} }
|
注意事项
- 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快.
- 关键字分布不均匀的情况下,该方法不一定比折半查找要好
斐波那契(黄金分割法)查找算法
- 黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神奇的数字,会带来意向不大的效果。
- 斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618
工作原理
斐波那契查找应用案例
请对一个有序数组进行斐波那契查找{1,8,10,89,1000,1234},输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
| import java.util.Arrays;
public class FibonacciSearch { public static int maxSize = 20;
public static void main(String[] args) { int[] arr = {1, 8, 10, 89, 1000, 1234};
int search = fibSearch(arr, 10); System.out.println(search); }
public static int[] fibo() { int[] fb = new int[maxSize]; fb[0] = 1; fb[1] = 1; for (int i = 2; i < maxSize; i++) { fb[i] = fb[i - 1] + fb[i - 2]; } return fb; }
public static int fibSearch(int[] arr, int key) { int low = 0; int high = arr.length - 1; int k = 0; int mid; int[] f = fibo(); while (high > f[k] - 1) { k++; } int[] temp = Arrays.copyOf(arr, f[k]);
for (int i = high + 1; i < temp.length; i++) { temp[i] = arr[high]; }
while (low <= high) { mid = low + f[k - 1] - 1; if (key < temp[mid]) { high = mid - 1;
k--; } else if (key > temp[mid]) { low = mid + 1;
k -= 2; } else { if (mid <= high) { return mid; } else { return high; } } } return -1; } }
|
有点难理解