青岛广告设计与制作公司,锦绣大地seo,数据库wordpress,上海外贸综合服务平台【数据结构】查找
数据结构中#xff0c;有顺序查找、二分查找、散列查找、插值查找、斐波那契额查找
1.顺序查找 条件#xff1a;待查找的元素与数组中的元素按顺序排列。算法#xff1a;从数组的第一个元素开始#xff0c;逐个比较#xff0c;直到找到目标元素或遍历完…【数据结构】查找
数据结构中有顺序查找、二分查找、散列查找、插值查找、斐波那契额查找
1.顺序查找 条件待查找的元素与数组中的元素按顺序排列。算法从数组的第一个元素开始逐个比较直到找到目标元素或遍历完整个数组。 java代码 public static int sequentialSearch(int[] arr,int target){for(int i0;iarr.length;i){if(arr[i]target){return i;}}return -1;}2.二分查找 条件待查找的元素与数组中的元素按顺序排列且数组已经排好序有序。 算法在有序数组中取中间位置的元素与目标元素进行比较如果相等则返回中间位置的下标如果目标元素比中间位置的元素小则在左半部分继续查找如果目标元素比中间位置的元素大则在右半部分继续查找。重复以上步骤直到找到目标元素或区间为空。 java代码
public static int binarySearch(int[] arr,int target){int left 0;int rightarr.length-1;while(leftright){int mid left(right-left)/2;if(arr[mid]target){return mid;} else if (targetarr[mid]) {rightmid-1;}else{left mid1;}}return -1;
}3.散列查找 条件待查找的元素存储在一个哈希表中。 算法通过哈希函数将待查找的元素映射到一个桶中然后遍历桶中的元素进行比较直到找到目标元素或遍历完所有桶。 java代码
public static void hashSearch(HashtableInteger, String table, int key) {int index table.get(key);if (index ! -1) {System.out.println(Found key at index index);} else {System.out.println(Not found key);}
}4.插值查找 条件待查找的元素存储在一个已排序的数组中但相邻元素之间的间隔不均匀。 算法通过计算待查找元素在数组中的大概位置然后在这个位置附近进行线性查找。 java代码
public static int interpolationSearch(int[] arr, int low, int high, int target) {while (low high target arr[low] target arr[high]) {int pos low ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);if (arr[pos] target) {return pos;}if (arr[pos] target) {low pos 1;} else {high pos - 1;}}return -1;
}5.斐波那契查找 条件待查找的元素存储在一个有序序列中每个元素都与前两个元素有关系。 算法通过递归方式计算待查找元素的位置直到找到目标元素或序列中没有更多元素。 java代码
public class FibonacciSearch {public static int fibonacciSearch(int[] arr, int key) {int low 0;int high arr.length - 1;int k 0; // 斐波那契数列的下标int[] fib FibonacciArr(arr.length);// 找到大于等于数组长度的最小斐波那契数列元素while (arr.length fib[k] - 1) {k;}// 将数组扩展到斐波那契数列元素的长度int[] temp Arrays.copyOf(arr, fib[k] - 1);// 将扩展部分用数组最后一个元素填充for (int i arr.length; i temp.length; i) {temp[i] arr[arr.length - 1];}// 查找过程while (low high) {int mid low fib[k - 1] - 1;if (key temp[mid]) {high mid - 1;k - 1;} else if (key temp[mid]) {low mid 1;k - 2;} else {return Math.min(mid, arr.length - 1);}}return -1;}// 生成斐波那契数列private static int[] FibonacciArr(int n) {int[] fib new int[n];fib[0] 1;fib[1] 1;for (int i 2; i n; i) {fib[i] fib[i - 1] fib[i - 2];}return fib;}
}
