Java查找算法练习(2024.7.23)

        顺序查找

package SearchExercise20240723;
import java.util.Scanner;
public class SearchExercise {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入%d个元素", i + 1);array[i] = sc.nextInt();}System.out.println("请输入想要查找的元素");int key = sc.nextInt();int result = searchElement(array, key);if (result != -1) {System.out.println("成功找到");System.out.printf("该元素的下标是%d", result);} else {System.out.println("数组中没有该元素");}}public static int searchElement(int[] array, int key) {for (int i = 0; i < array.length; i++) {if (array[i] == key) {return i;}}return -1;}// 这是最简单的查找，效率为O(n)
}

        二分查找

package SearchExercise20240723;
import java.util.Scanner;
public class SearchExercise2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入第%d个元素", i + 1);array[i] = sc.nextInt();}System.out.println("请输入你想要查找的元素");int key = sc.nextInt();int flag = searchImprove(array, key);if (flag == -1) {System.out.println("数组中没有该元素");} else {System.out.println("查找成功，下标是" + flag);}}// 二分查找，使用十分的广泛，时间复杂度是O(log2n)，但是二分查找需要元素有序才可以使用public static int searchImprove(int[] array, int key) {int low = 0;int high = array.length - 1;while (low <= high) {int mid = (low + high) / 2;if (array[mid] > key) {high = mid - 1;} else if(array[mid] < key) {low = mid + 1;} else {return mid;}}return -1;}
}

        插值查找（二分查找的改进）

package SearchExercise20240723;
import java.util.Scanner;
public class SearchExercise3 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入第%d个元素", i + 1);array[i] = sc.nextInt();}System.out.println("请输入你想要查找的元素");int key = sc.nextInt();int flag = searchImprove(array, key);if (flag == -1) {System.out.println("数组中没有该元素");} else {System.out.println("查找成功，下标是" + flag);}}// 插值查找，通过将每次查找的点进行改进（mid），让mid值的变化更靠近关键字key，可以间接的减少比较的次数// 细节：和二分查找几乎一样，除了对于mid的计算不同，所以说插值查找也需要查找表有序// 并且对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多，// 但是对于分布不均匀的查找表，插值查找不建议选择public static int searchImprove(int[] array, int key) {int low = 0;int high = array.length - 1;while (low <= high) {int mid = low+((key-array[low])*(high-low))/(array[high]-array[low]);// 改变了mid的计算，使得让mid的变化更加接近查找关键字if (array[mid] > key) {high = mid - 1;} else if (array[mid] < key) {low = mid + 1;} else {return mid;}}return -1;}
}

         斐波那契查找

package SearchExercise20240723;
import java.util.Arrays;
import java.util.Scanner;
public class SearchExercise4 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入第%d个元素", i + 1);array[i] = sc.nextInt();}System.out.println("请输入你想要查找的元素");int key = sc.nextInt();int result = fibSearch(key, array);if (result == -1) {System.out.println("数组中没有这个元素");} else {System.out.println("成功找到，下标是" + result);}}public static int[] creatFib() {int[] arr = new int[20];arr[0] = 1;arr[1] = 1;for (int i = 2; i < 20; i++) {arr[i] = arr[i - 1] + arr[i - 2];}return arr;}public static int fibSearch(int key, int[] arr) {int low = 0;int high = arr.length - 1;//表示斐波那契数分割数的下标值int index = 0;int mid = 0;//调用斐波那契数列int[] f = creatFib();//获取斐波那契分割数值的下标while (high > (f[index] - 1)) {index++;}//因为f[k]值可能大于a的长度，因此需要使用Arrays工具类，构造一个新法数组，并指向temp[],不足的部分会使用0补齐int[] temp = Arrays.copyOf(arr, f[index]);//实际需要使用arr数组的最后一个数来填充不足的部分for (int i = high + 1; i < temp.length; i++) {temp[i] = arr[high];}//使用while循环处理，找到key值while (low <= high) {mid = low + f[index - 1] - 1;if (key < temp[mid]) {//向数组的前面部分进行查找high = mid - 1;/*对k--进行理解1.全部元素=前面的元素+后面的元素2.f[k]=k[k-1]+f[k-2]因为前面有k-1个元素没所以可以继续分为f[k-1]=f[k-2]+f[k-3]即在f[k-1]的前面继续查找k--即下次循环,mid=f[k-1-1]-1*/index--;} else if (key > temp[mid]) {//向数组的后面的部分进行查找low = mid + 1;index -= 2;} else {//找到了//需要确定返回的是哪个下标if (mid <= high) {return mid;} else {return high;}}}return -1;}
}

        分块查找

package SearchExercise20240723;
import java.util.Arrays;
import java.util.Scanner;
public class SearchExercise5 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("需要多大的数组?");int size = sc.nextInt();int[] array = new int[size];for (int i = 0; i < array.length; i++) {System.out.printf("请输入第%d个元素", i + 1);array[i] = sc.nextInt();}// 创建索引表int blockSize = (int)Math.sqrt(array.length);Block[] blocksArray = creatBlocksArray(array, blockSize);// 分块查找System.out.println("请输入要查找的元素");int key = sc.nextInt();int result = blockSearch(array, blocksArray, key);if (result == -1) {System.out.println("数组中无法找到该元素");} else {System.out.printf("成功找到，下标是%d", result);}}public static Block[] creatBlocksArray(int[] array, int blockSize) {int blockNumbers = (int)Math.ceil(array.length * 1.0 / blockSize);Block[] blockArray = new Block[blockNumbers];for (int i = 0; i < blockArray.length; i++) {int start = i * blockSize;int end = Math.min(start + blockSize, array.length);int maxKey = Arrays.stream(array, start, end).max().orElse(Integer.MIN_VALUE);blockArray[i] = new Block(start, end, maxKey);}return blockArray;}public static int blockSearch(int[] array, Block[] blocksArray, int key) {int blockIndex = -1;for (int i = 0; i < blocksArray.length; i++) {if (key <= blocksArray[i].getMaxKey()) {blockIndex = i;break;}}if (blockIndex == -1) {return -1;}int start = blocksArray[blockIndex].getStart();int end = blocksArray[blockIndex].getEnd();for (int i = start; i < end; i++) {if(array[i] == key){return i;}}return -1;}
}class Block{private int start;private int end;private int maxKey;public Block(int start, int end, int maxKey) {this.start = start;this.end = end;this.maxKey = maxKey;}public int getStart() {return start;}public void setStart(int start) {this.start = start;}public int getEnd() {return end;}public void setEnd(int end) {this.end = end;}public int getMaxKey() {return maxKey;}public void setMaxKey(int maxKey) {this.maxKey = maxKey;}
}