二分查找算法总结

一、简单的二分查找算法，代码如下：

1.  对参数的合法性进行检查，参数不合法时直接抛出异常。
2. 使用-1代表数组中不存在该元素
3. 计算中间元素时，使用int mid = left + ((right - left) >> 2) 代替int mid = (left + right)/2。因为left + right有可能会超出范围，使用位运算符性能相对会比除法运算符性能好。

// 最简单的二分查找，不包含重复元素
	public static <T extends Comparable<T>> int binarySearch1(T[] nums, T target) throws Exception {
		// 参数合法性检查
		if (nums == null)
			throw new Exception();

		int left = 0;
		int right = nums.length - 1;
		while (left <= right) {
			int mid = left + ((right - left) >> 2);
			if (nums[mid].compareTo(target) == 0) {
				return mid;
			} else if (nums[mid].compareTo(target) > 0) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return -1;
	}

上面的二分查找算法对于有重复元素时就会失效了，下面介绍几种二分查找变种

一、存在重复元素时查找给定值最左侧的索引

代码如下：

public static <T extends Comparable<T>> int binarySearch2(T[] nums, T target) throws Exception {
		if (nums == null)
			throw new Exception();
		int left = 0;
		int right = nums.length - 1;
		while (left <= right) {
			int mid = left + ((right - left) >> 2);
			if (nums[mid].compareTo(target) < 0) {
				left = mid + 1;
			} else if (nums[mid].compareTo(target) > 0) {
				right = mid - 1;
			} else {
				// mid已经找到最小索引
				// mid的前一个元素已经不等于target ，说明我们已经找到需要的最小索引
				if (mid == 0 || nums[mid - 1] != target) {
					return mid;
				} else {
					// 使右索引不断的像左侧逼近
					right = mid - 1;
				}
			}
		}
		return -1;
	}

二、存在重复元素时查找给定值最右侧的索引

和最左侧的分析差不多，唯一的差一点是nums[mid] == target 时处理逻辑，代码如下：

public static <T extends Comparable<T>> int binarySearch3(T[] nums, T target) throws Exception {
		if (nums == null)
			throw new Exception();
		int left = 0;
		int right = nums.length - 1;
		while (left <= right) {
			int mid = left + ((right - left) >> 2);
			if (nums[mid].compareTo(target) < 0) {
				left = mid + 1;
			} else if (nums[mid].compareTo(target) > 0) {
				right = mid - 1;
			} else {
				// mid已经是最大索引
				// mid的后一个元素已经不等于target ，说明我们已经找到需要的最大索引
				if (mid == nums.length - 1 || nums[mid + 1] != target) {
					return mid;
				} else {
					// 使左索引不断的像右侧逼近
					left = mid + 1;
				}
			}
		}
		return -1;
	}

三、查找第一个大于等于给定值的情况

1. 如果nums[mid]小于要查找的值，那么我们需要查找在[mid+1,right]之间，所以此时更新为left=mid+1
2. 如果nums[mid]大于等于给定值tagrget,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素，如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值。相反
3. 如果nums[mid-1]也是大于等于查找的值，那么说明查找的元素在[left,mid-1]之间，所以我们需要将right更新为mid-1

代码如下：

// 查找第一个大于等于给定值的情况
	public static <T extends Comparable<T>> int binarySearch4(T[] nums, T target) throws Exception {
		if (nums == null)
			throw new Exception();
		int left = 0;
		int right = nums.length - 1;
		while (left <= right) {
			int mid = left + ((right - left) >> 1);
			if (nums[mid].compareTo(target) < 0) {
				left = mid + 1;
			} else {
				// 如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值
				if (mid == 0 || nums[mid - 1].compareTo(target) < 0) {
					return mid;
				} else {
					// 如果nums[mid-1]也是大于等于查找的值
					right = mid - 1;
				}
			}
		}
		return -1;
	}

四、查找最后一个小于等于给定值的情况

1. 如果nums[mid]大于给定的target，那么我们需要查找的值在[left,mid-1]之间
2. 如果nums[mid]小于等于查找的值，则进行判断

代码如下

// 查找最后一个小于等于给定值的元素
	public static <T extends Comparable<T>> int binarySearch5(T[] nums, T target) throws Exception {
		if (nums == null)
			throw new Exception();
		int left = 0;
		int right = nums.length - 1;
		while (left <= right) {
			int mid = left + ((right - left) >> 1);
			// 如果nums[mid]大于给定的target，那么我们需要查找的值在[left,mid-1]之间
			if (nums[mid].compareTo(target) > 0) {
				right = mid - 1;
			} else {
				// 如果已经是最后一个元素或者mid的后一个已经大于target，则直接返回mid
				if (mid == nums.length - 1 || nums[mid + 1].compareTo(target) > 0)
					return mid;

				// 否则，继续在[mid+1,right]之间查找
				left = mid + 1;
			}
		}
		return -1;
	}

个人记录，如有错误，请帮指正，谢谢！

最后

以上就是机灵康乃馨为你收集整理的二分查找算法总结的全部内容，希望文章能够帮你解决二分查找算法总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。