前言：本文深入讨论二分查找在闭区间[]的写法，开区间()的写法，半闭半开[)区间的写法，这三种写法的区别。以及查找元素时如何处理条件大于>，大于等于>=，小于<，小于等于<=，这四种情况。
问题：给你一个有序排列的数组nums={4,5,5,7,8,8,8,9,15,20}，请你找到第一个>=8的数的位置，如果所有数都<8，返回数组长度。
一、二分查找在闭区间[]的写法
暴力解法用2层for循环去遍历，时间复杂度为O(n^2)，且没有用到数组是有序的这个性质，不推荐
推荐：我们可以定义2个指针L和R，即闭区间[L,R],M指向当前正在询问的数，红色染色表示false，本题即<8；蓝色染色表示true，即>=8；白色背景表示不确定。由于是闭区间，所以针对例题数组，L=0，R=n-1=9，m=L+(R-L)/2=0+(9-0)/2=4(向下取整)
循环不变量：L-1始终是红色；R-1始终是蓝色。
private int lowerBound(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n - 1; // [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // [mid+1, right]
} else {
right = mid - 1; // [left, mid-1]
}
}
return left; // left一定是指向
}
二、二分查找在半闭半开[)区间的写法
private int lowerBound2(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n; // [left, right)
while (left < right) {
// ==也行
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // [mid+1, right)
} else {
right = mid; // [left, mid)
}
}
return left; // left 或者 right都行
}
三、二分查找在开区间()的写法
private int lowerBound3(int[] nums, int target) {
int n = nums.length;
int left = -1;
int right = n; // (left, right)
while (left + 1< right) {
// ==也行
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid; // (mid, right)
} else {
right = mid; // (left, mid)
}
}
return right; // left 或者 right都行
}
以上三种方法萝卜青菜各有所爱。
讨论完>=。那么>，即可转化为>=x+1。<即(>=x)-1。<=即(>x)-1也就是(>=x+1)-1
这里举例一题闭区间[]，原题目leetcode链接
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
int start = lowerBound(nums, target);
if (start == n || nums[start] != target)
return new int[]{
-1,-1};
int end = lowerBound(nums, target + 1) - 1; // 找到start说明数组中一定有target，所以一定存在end
return new int[]{
start, end};
}
private int lowerBound(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n - 1; // [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // [mid+1, right]
} else {
right = mid - 1; // [left, mid-1]
}
}
return left;
}
“永无止境，诸君共勉”
