数据结构和算法——查找算法
目录
线性查找法
二分查找法
插值查找法
斐波那契查找法
线性查找法
可以是有序的，也可以是无序的。
public class SeqSearch {public static void main(String[] args) {int[] arr = new int[]{1, 9, 11, -1, 34, 89};int res = seqSearch(arr, 34);}public static int seqSearch(int[] arr, int n) {for (int i = 0; i < arr.length; i++) {if (arr[i] == n) {return i;}}return -1;}
}
二分查找法
也叫折半查找，数组必须有序。
public class BinarySearch {public static void main(String[] args) {int[] arr = new int[]{2, 2, 4, 4, 5};
// int res = binarySearch(arr, 6);List list = binarySearchPlus(arr, 6);}public static int binarySearch(int[] arr, int n) {int l = 0;int r = arr.length - 1;while (l <= r) {int m = (l + r) / 2;if (n < arr[m]) {r = m - 1;} else if (n > arr[m]) {l = m + 1;} else if (n == arr[m]) {return m;} else {return -1;}}return -1;}public static ArrayList binarySearchPlus(int[] arr, int n) {int l = 0;int r = arr.length - 1;while (l <= r) {int m = (l + r) / 2;if (n < arr[m]) {r = m - 1;} else if (n > arr[m]) {l = m + 1;} else if (n == arr[m]) {ArrayList<Integer> list = new ArrayList<>();list.add(m);for (int i = m - 1; i >= 0 && n == arr[i]; i++) {list.add(i);}for (int i = m + 1; i < arr.length && n == arr[i]; i++) {list.add(i);}Collections.sort(list);return list;} else {return null;}}return null;}
}