Java算法之二分查找法

本章介绍Java实现二分查找法，欢迎各位同学转载，但转载务必注明出处：https://blog.csdn.net/qq_35101450/article/details/89194473，谢谢~

什么是二分查找法

二分查找法也叫折半查找法，是一种效率比较高的查找方法，它要求被查找的数组是有序的。

二分查找原理

案例：大家应该都玩过猜数字游戏吧，比如我们要从1到100找出某一个数，一般我们会先从50开始猜，然后对方会告诉你猜的数比50大或者比50小，如果比50大，那我们肯定会猜一个介于51到100之间的数，如果比50小，我们肯定会猜一个介于0到49之间的数。假设比50小，我们一般会猜是25。。。以此类推，我们猜的数与目标就会越来越近，直至猜到这个数。这个案例其实原理和二分查找是一样的。

原理：我们取数组中间位置的值（下称中值），与要查找的值进行比较，若小于要查找的值，则在中值右边的数据中继续查找；若中值大于要查找的值，则在中值左边的数据中继续查找；若等于要查找的值，则直接返回。查找操作是一个循环的过程，我们依次会在中值左边或者右边数据中进行查找，直至中值等于要查找的数据。

原理图解

Java算法之二分查找法

代码示例：

我分别用递归和循环两种方式实现。

package String;

public class BinarySearchDemo {
	public static void main(String[] args) {
		int[] arr = { 12, 34, 56, 78, 90, 96, 98, 99 };
		boolean isExisted = binarySearch(99, arr, 0, arr.length - 1);
		boolean isHased = binarySearch(1, arr);
		System.out.println("isExisted ==  " + isExisted);
		System.out.println("isHased ==  " + isHased);
	}

	// 递归实现二分查找
	private static boolean binarySearch(int data, int[] arr, int minIndex, int maxIndex) {
		int midIndex = (minIndex & maxIndex) + ((minIndex ^ maxIndex) >> 1);
		if (data < arr[minIndex] || data > arr[maxIndex] || minIndex > maxIndex) {
			return false;
		}
		if (data > arr[midIndex]) {
			return binarySearch(data, arr, midIndex + 1, maxIndex);
		} else if (data < arr[midIndex]) {
			return binarySearch(data, arr, minIndex, midIndex - 1);
		} else {
			return true;
		}
	}

	// 循环实现二分查找
	private static boolean binarySearch(int data, int[] arr) {
		int minIndex = 0;
		int maxIndex = arr.length - 1;
		int midIndex;

		while (minIndex <= maxIndex) {
			midIndex = (minIndex & maxIndex) + ((minIndex ^ maxIndex) >> 1);
			if (data > arr[midIndex]) {
				minIndex = midIndex + 1;
			} else if (data < arr[midIndex]) {
				maxIndex = midIndex - 1;
			} else {
				return true;
			}
		}
		return false;
	}
}

运行结果：

isExisted == true
isHased == false

细心的同学应该已经看到我这里在取中值索引时，采用(minIndex & maxIndex) + ((minIndex ^ maxIndex) >> 1)的方法，是不是一头雾水，为什么不用(minIndex+maxIndex)/2取中值？还能不能好好玩了~这里我简单解释一下。如果我们用(minIndex+maxIndex)/2取中值，在maxIndex=Integer.MAX_VALUE，minIndex>0时，它俩相加就会出现溢出现象。而(minIndex & maxIndex) + ((minIndex ^ maxIndex) >> 1)这个方法的原理是把minIndex和maxIndex里对应的每一位（指二进制位）都分成三类，每一类分别计算平均值，最后汇总。其中，一类是minIndex,maxIndex对应位都是1，用minIndex&maxIndex计算其平均值；一类是minIndex,maxIndex中对应位有且只有一位是1，用(minIndex^maxIndex)>>1计算其平均值；还有一类是minIndex,maxIndex中对应位均为0，无须计算。通过位运算，既避免了数据过大造成的溢出现象，有提高了程序运行效率。

好了，先科普这么多了，欢迎新老司机留言评论，指出我写的不对的地方，大家一起进步~

Java算法之二分查找法

什么是二分查找法

相关推荐