做杂志的网站有哪些,哈尔滨网站备案手续,北京做药流凤凰网站,莆田做网站【数据结构】查找
数据结构中#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 static int fibonacciSearch(int[] arr, int target) {int n arr.length;if (n 0) {return -1;}int first 0;int second 1;int count 0;while (count n) {int temp first second;if (temp n) {temp first;}if (arr[temp] target) {return temp;} else if (arr[temp] target) {first temp;count;} else {second temp;count;}}return -1;
}
