【数据结构】查找

【数据结构】查找

数据结构中，有顺序查找、二分查找、散列查找、插值查找、斐波那契额查找

1.顺序查找

• 条件：待查找的元素与数组中的元素按顺序排列。
• 算法：从数组的第一个元素开始，逐个比较，直到找到目标元素或遍历完整个数组。

java代码

  public static int sequentialSearch(int[] arr,int target){for(int i=0;i<arr.length;i++){if(arr[i]==target){return i;}}return -1;}

2.二分查找

• 条件：待查找的元素与数组中的元素按顺序排列，且数组已经排好序，有序。

• 算法：在有序数组中，取中间位置的元素与目标元素进行比较，如果相等则返回中间位置的下标；如果目标元素比中间位置的元素小，则在左半部分继续查找；如果目标元素比中间位置的元素大，则在右半部分继续查找。重复以上步骤，直到找到目标元素或区间为空。

java代码

public static int binarySearch(int[] arr,int target){int left =0;int right=arr.length-1;while(left<=right){int mid = left+(right-left)/2;if(arr[mid]==target){return mid;} else if (target<arr[mid]) {right=mid-1;}else{left = mid+1;}}return -1;
}

3.散列查找

• 条件：待查找的元素存储在一个哈希表中。

• 算法：通过哈希函数将待查找的元素映射到一个桶中，然后遍历桶中的元素进行比较，直到找到目标元素或遍历完所有桶。

java代码

public static void hashSearch(Hashtable<Integer, 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;}
}