常见的查找算法

发布时间:2024年01月15日

前提:除了线性查找外,下面的其他查找算法适用于有序数组(以从小到大为例)

一、线性查找

/**
	 * 这里若要查找重复出现的数,可以把索引放入到一个集合中
	 * @param arr
	 * @param value
	 * @return 如果没有找到,则返回 -1
	 */
	public static int seqSearch(int[] arr, int value) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == value) {
				return i;
			}
		}
		return -1;
	}

二、二分查找

public static int binarySearch(int[] arr, int left, int right, int value) {
		// 数组中不含有指定的数
		if (left > right) {
			return -1;
		}

		int midIndex = (left + right) / 2;// 中间索引
		int midValue = arr[midIndex];
		if (value > midValue) {// 向右递归
			return binarySearch(arr, midIndex + 1, right, value);
		} else if (value < midValue) {// 向左递归
			return binarySearch(arr, left, midIndex - 1, value);
		} else {
			return midIndex;
		}
	}

?上面的代码,对于重复出现的元素没有处理,下面的代码将作出处理

// 完成一个课后思考题
	// int[] arr = { 1, 8, 10, 89, 1000, 1000, 1234 };
	// 解决重复元素全部输出的问题,比如1000
	// 思路:
	// 在找到对应的值后先不要返回,分别向右和左进行查找,看看有没有和他相等的值,有的话就放到一个集合中
	public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int value) {
		System.out.println("查找的次数");
		// 数组中不含有指定的数
		if (left > right) {
			return new ArrayList<Integer>();
		}

		int midIndex = (left + right) / 2;// 中间索引
		int midValue = arr[midIndex];
		if (value > midValue) {// 向右递归
			return binarySearch2(arr, midIndex + 1, right, value);
		} else if (value < midValue) {// 向左递归
			return binarySearch2(arr, left, midIndex - 1, value);
		} else {

			// 向左查找
			ArrayList<Integer> resIndexList = new ArrayList<Integer>();
			int leftIndex = midIndex - 1;
			while (true) {
				if (leftIndex < 0 || arr[leftIndex] != value) {// 因为数组是有序数组,所以若向左没有发现,那么退出循环
					break;
				}
				// 否则,就将对应的索引加入到集合中
				resIndexList.add(leftIndex);
				leftIndex--;
			}
			resIndexList.add(midIndex);// 将第一次找到的索引加入到集合中

			// 向右查找
			int rightIndex = midIndex + 1;
			while (true) {
				if (leftIndex > arr.length - 1 || arr[rightIndex] != value) {// 若向右没有发现,那么退出循环
					break;
				}
				// 否则,就将对应的索引加入到集合中
				resIndexList.add(rightIndex);
				rightIndex++;
			}
			return resIndexList;
		}
	}

尝试用二分法做,提高性能?

LeetCode高频题69. x 的平方根,二分法搞定,非常简单_分治法求解计算并返回x的平方根。-CSDN博客

力扣287题(用二分法做,提高性能)

三、插值查找

本质:将二分查找的midIndex(中间索引)改成:

int midIndex = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);

public static int binarySearch1(int[] arr, int left, int right, int value) {
		// 数组中不含有指定的数
		// arr[left] > value || arr[right] < value不能少,否则midIndex过大,可能会越界
		System.out.println("查找的次数");
		if (left > right || arr[left] > value || arr[right] < value) {
			return -1;
		}

		int midIndex = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);// 中间索引
		int midValue = arr[midIndex];
		if (value > midValue) {// 向右递归
			return binarySearch1(arr, midIndex + 1, right, value);
		} else if (value < midValue) {// 向左递归
			return binarySearch1(arr, left, midIndex - 1, value);
		} else {
			return midIndex;
		}
	}

上面的代码,对于重复出现的元素没有处理,下面的代码将作出处理

// 解决重复元素全部输出的问题
	public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int value) {
		// 数组中不含有指定的数
		// arr[left] > value || arr[right] < value不能少,否则midIndex过大,可能会越界
		System.out.println("查找的次数");
		if (left > right || arr[left] > value || arr[right] < value) {
			return new ArrayList<Integer>();
		}

		int midIndex = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);// 中间索引
		int midValue = arr[midIndex];
		if (value > midValue) {// 向右递归
			return binarySearch2(arr, midIndex + 1, right, value);
		} else if (value < midValue) {// 向左递归
			return binarySearch2(arr, left, midIndex - 1, value);
		} else {
			// 向左查找
			ArrayList<Integer> resIndexList = new ArrayList<Integer>();
			int leftIndex = midIndex - 1;
			while (true) {
				if (leftIndex < 0 || arr[leftIndex] != value) {// 因为数组是有序数组,所以若向左没有发现,那么退出循环
					break;
				}
				// 否则,就将对应的索引加入到集合中
				resIndexList.add(leftIndex);
				leftIndex--;
			}
			resIndexList.add(midIndex);// 将第一次找到的索引加入到集合中

			// 向右查找
			int rightIndex = midIndex + 1;
			while (true) {
				if (leftIndex > arr.length - 1 || arr[rightIndex] != value) {// 若向右没有发现,那么退出循环
					break;
				}
				// 否则,就将对应的索引加入到集合中
				resIndexList.add(rightIndex);
				rightIndex++;
			}
			return resIndexList;
		}
	}

?注意:插值查找算法适用于数据分布均匀,数组中数量较多的数组,对于数据分布不均匀的数组,此方法未必有二分查找算法好;

四、斐波那契查找算法(黄金分割搜索算法)

// 先得到斐波那契数列
	// 因为后面要用到mid = low + F(k-1)-1
	public static int[] fib() {
		int[] f = new int[20];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < maxSize; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
		return f;
	}

	/**
	 * 
	 * @param a   要查找的数组
	 * @param key 要找的值
	 * @return 如果找到,则返回下标,否则返回-1
	 */
	// 开始编写斐波那契查找算法
	public static int fibSearch(int[] a, int key) {
		int low = 0;
		int high = a.length - 1;// high是最大的索引
		int k = 0;// 表示斐波那契的数列的下标
		int mid = 0;// 存放mid的值
		int[] f = fib();// 获取当前的斐波那契数列

		// 获取到当前斐波那契的下标,即当斐波那契数列中的 一个数 大于或等于 数组的长度时才停止
		while (f[k] <= high + 1) {// high + 1为整个数组的长度
			k++;
		}

		// 找到k的值
		// 因为f[k]的值可能会大于数组a的长度,所以要将数组a给补全,
		// 即让数组a的长度和f[k]的值一样(用Arrays提供的一个方法)
		int[] temp = Arrays.copyOf(a, f[k]);// 长度不够,用零来凑
		// 将数组后面几位0赋值成 数组对应的最后一位的值
		for (int i = high + 1; i < temp.length; i++) {
			temp[i] = a[high];
		}

		// 使用while循环来找到我们的key
		while (low <= high) {
			mid = low + f[k - 1] - 1;// 公式
			if (key < temp[mid]) {// 向数组的左边找
				high = mid - 1;
				k--;
				// 为什么是k--
				// 1.全部元素 = 前面的元素 + 后面的元素
				// 即 f[k] = f[k-1] + f[k-2]
				// 2.因为前面有f[k-1]个元素,所以可以继续拆分f[k-1] = f[k-2] + f[k-3]
				// 即在f[k-1]的前面继续查找
				// 即下次循环 mid = f[k-1-1]-1
			} else if (key > temp[mid]) {
				low = mid + 1;
				k -= 2;
				// 为什么是 k-= 2
				// 1.全部元素 = 前面的元素 + 后面的元素
				// 即 f[k] = f[k-1] + f[k-2]
				// 2.因为后面有f[k-2]个元素,所以可以继续拆分f[k-2] = f[k-3] + f[k-4]
				// 即在f[k-5]的前面继续查找
				// 即下次循环mid = f[k-1-2]-1
			} else {
				// 此时key = temp[mid] 找到
				// 需要确定,返回的是哪一个下标
				// 要返回较小的值,因为temp数组是我们自己补全的 mid可能会大于high
				if (mid <= high) {
					return mid;
				} else {
					return high;
				}

			}
		}
		return -1;// 上面的全部执行完后,如果还没有找到,那么就返回-1
	}

?上面的代码只实现了对一个元素的输出

思考:用斐波那契查找算法实现输出? 全部重复元素? 的索引。

比如:int[] arr = { 1, 8, 10, 89, 1000, 1000, 1234 };

查找 1000,返回索引

输出:[4? 5]

文章来源:https://blog.csdn.net/liusaidh/article/details/135562653
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。