在不重复升序数组查找目标值
解法1
public static int binarySearchV1(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 遍历区间: [left,right]
int left = 0;
int right = nums.length - 1; // 注意
// 终止条件 left == right + 1
while (left <= right) {
// 相比(left+right)/2可以避免整型溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
说明：
① right的初始值为nums.length-1，表示此次二分查找的区间为[left,right]，为左闭右闭区间
②根据①双闭区间的特性，while(left <= right)，满足进入循环体条件 left <= right ，此时终止循环的条件为 left = right + 1，区间为[right+1,right]为空区间，不存在未遍历元素
③循环体内对left和right的重新赋值，left=mid+1表达式对应新的区间为[mid+1,right]; right = mid-1表达式对应新的区间[left,mid-1]，两个区间都不包含nums[mid]元素，因为这个元素已经在if (nums[mid] == target)判断分支处理过
解法2
public static int binarySearchV2(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍历区间: [left,right]
int left = 0;
int right = nums.length - 1; // 注意
// 终止条件为left == right
while (left < right) { // 注意和解法1的区别
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// 注意和解法1的区别
return nums[left] == target ? left : -1;
}
说明：
本题和解法1区间同为[left,right]，但是进入循环的条件却是while(left < right)，那么终止条件为left == right，这将导致到最后存在区间[left,left]，剩余一个元素未被遍历
①对于剩下最后一个元素未被二分查找遍历的情况，此时left=right，因此最后打补丁多判断一次nums[left]==target
解法3
public static int binarySearchV3(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍历区间: [left,right)
int left = 0;
int right = nums.length; // 注意
// 终止条件为left == right+1
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return -1;
}
说明：
本解法采取左闭右开区间，二分查找区间 [left,right)，同时搭配进入循环条件while(left < right)，此时终止循环的条件为 left == right，区间为[left,left)为一个空区间
①不同于解法1和解法2，循环体内right=mid，而不是right=mid-1，这是因为查找区间左边为开区间，此时新的查找区间为[left,mid)，同样nums[mid]不再参与下一轮二分查找
在可能重复升序数组查找目标值左边界
以下不再对上文已经解释过的内容重新说明，关于开闭区间与left、right的重新取值以上文为准
先来看两个初步解法
解法1
public static int leftBoundV1(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍历区间: [left,right]
int left = 0;
int right = nums.length - 1;
// 终止条件left == right+1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return left;
}
说明：
①不同于之前查找目标值，查找左边界在 if (nums[mid] == target) 符合条件时，采取进一步压缩右边界 right = mid-1
②为什么最后返回left，由于循环终止条件left = right+1, 当查找到左边界时，一定满足 if (nums[mid] == target)条件，此时会执行 right = mid -1，由于mid为符合条件的答案，此时mid=right+1=left
解法2
public static int leftBoundV2(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍历区间: [left,right)
int left = 0;
int right = nums.length;
// 终止条件left == right
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left;
}
说明：
本解法就是对解法1进行区间[left,right)的改造，因此在 if (nums[mid] == target) 符合条件时，压缩右边界 right = mid
①解释为什么返回left，由于左边界一定符合条件 if (nums[mid] == target) ，此时会执行语句 right = mid，又因为终止循环条件为 left == right , 此时存在表达式left == mid == right，所以返回left也可以
解法1和解法2看似完美，但是没有解决以下问题：
在数组nums={1,2,3,4,5} 里查找6，将返回5，很明显nums[5]并不是6
理解这个问题前，先讨论下解法1和解法2left和right的取值范围
解法1：
由于二分查找mid区间为[left,right]即[0,nums.length-1]
left初始值0，循环体内存在表达式left=mid+1区间为[1，nums.length]，合并之后left的区间为[0,nums.length]
right初始值nums.length-1,循环体内存在表达式right=mid-1区间为[-1，nums.length-2]，合并之后right的区间为[-1,nums.length-1]解法2：
由于二分查找mid区间为[left,right)即[0,nums.length)
left初始值0，循环体内存在表达式left=mid+1区间为[0，nums.length+1)，合并之后left的区间为[0,nums.length+1) 即 [0,nums.length]
right初始值nums.length，循环体内存在表达式right=mid区间为[0，nums.length)，合并之后right的区间为[0,nums.length) 即 [0,nums.length]
通过上述总结，发现left的区间总为[0,nums.length]，其实可以将left值理解为数组nums中有多少个元素小于target，那么在数组nums={1,2,3,4,5} 里查找6，返回5的问题就很好理解了，如下图最后返回left=1，表示有一个元素小于目标2
那么可以对解法1进行修改（解法2修改类同，不赘述）
public static int leftBoundV3(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍历区间: [left,right]
int left = 0, right = nums.length - 1;
// 终止条件: left = right + 1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) { // 收缩右侧边界
right = mid - 1;
} else if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right], nums[mid]不参与下一轮
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]，nums[mid]不参与下一轮
right = mid - 1;
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
说明：
既然left取值区间为[0,nums.length]，那么新增判断left是否超过nums.length-1
同时，由于left表示数组nums内有多少元素小于target，不代表target一定在数组内，新增判断nums[left]!=target
在可能重复升序数组查找目标值右边界
和查找左边界一样，先来看初步解法
解法1
public static int rightBoundV1(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍历区间: [left,right]
int left = 0, right = nums.length - 1;
// 终止条件left == right+1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return left - 1; // 注意
}
说明：
①为什么左边界返回left，右边界返回left-1?
由于最后一个满足target的右边界满足条件 if (nums[mid] == target) ，此时执行left = mid +1，nums[target]==target，那么这个时候存在表达式left-1=mid=right，因此最后返回left-1
②left、right区间？
由于mid 取值区间 [0,nums.length-1]
left初始值0，mid+1取值区间为[1,nums.length]，因此合并后left区间为[0,nums.length]
right 初始值nums.length-1，mid-1取值区间为[-1,nums.length-2]，因此合并后right区间 [-1,nums.length-1]
解法2
public static int rightBoundV2(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 二分查找遍历区间: [left,right)
int left = 0, right = nums.length;
// 终止条件left == right
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}
说明：
①为什么左边界返回left，右边界返回left-1?
同解法1
②left、right区间？
由于mid 取值区间 [0,nums.length)
left初始值0，mid+1取值区间为[1,nums.length+1)，因此合并后left区间为[0,nums.length+1)，即[0,nums.length]
right 初始值nums.length，mid取值区间为[0,nums.length)，因此合并后right区间 [0,nums.length]
③可以看到无论是双闭区间还是左闭右开区间，求右边界统一解答都是left-1（right则由于循环结束条件不同而不同）
最后同样需要处理一下target不在数组内部的情况
解法3
public static int rightBoundV3(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
// 搜索区间 [left,right]
int left = 0, right = nums.length - 1;
// 终止条件 left = right+1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
if (right < 0 || nums[right] != target) { // 注意
return -1;
}
return right;
}
说明：
①和解法1一样，本题left区间为[0,nums.length]，right区间[-1,nums.length-1]，循环终止条件left = right+1，此时解为 mid = left-1=right，因此需要判断right是否小于0
②同时需要判断nums[right] != target，排除target不在数组的情况，此时的left-1或者right可以理解为有多少个元素小于等于target
