二分查找BinarySearch

二分查找BinarySearch

概述

二分查找，高效易用，但边界问题常常让人犯愁。

公式

    public int searchInsert(int[] nums, int target) {// 保证颜色纯粹性int left = -1;int right = nums.length;while (left + 1 != right) {int mid = (left + right) / 2;if (isBlue(mid)) {left = mid;} else {right = mid;}}return left or right;}

• 找第一个：左边不满足，return right
• 找最后一个：右边不满足，return left

原理

找蓝红边界
数组找边界
0-4为Blue
5-8为Red
【01234 5678】
l和r两个指针，分别指示蓝色和红色的区域，
每次折半拆分，确定一半未知区域的颜色。

小试牛刀

private static int firstGreaterFive(int[] arr) {int left = -1;int right = arr.length;while (left + 1 != right) {int mid = (left + right) / 2;if (arr[mid] <= 5) {left = mid;} else {right = mid;}}return right;}private static int firstGreaterEqualFive(int[] arr) {int left = -1;int right = arr.length;while (left + 1 != right) {int mid = (left + right) / 2;if (arr[mid] < 5) {left = mid;} else {right = mid;}}return right;}private static int lastLessFive(int[] arr) {int left = -1;int right = arr.length;while (left + 1 != right) {int mid = (left + right) / 2;if (arr[mid] < 5) {left = mid;} else {right = mid;}}return left;}private static int lastLessEqualFive(int[] arr) {int left = -1;int right = arr.length;while (left + 1 != right) {int mid = (left + right) / 2;if (arr[mid] <= 5) {left = mid;} else {right = mid;}}return left;}public static void main(String[] args) {int[] arr = {0, 1, 2, 3, 4, 5, 5, 5, 8, 9};Assert.isTrue(firstGreaterFive(arr) == 8, "查找第一个大于5的值");Assert.isTrue(firstGreaterEqualFive(arr) == 5, "查找第一个大于等于5的值");Assert.isTrue(lastLessFive(arr) == 4, "查找最后一个小于5的值");Assert.isTrue(lastLessEqualFive(arr) == 7, "查找最后一个小于等于5的值");}

reference