二分查找有两种实现方式：
递归实现，循环迭代实现，相比而言，迭代循环实现比较有难度
递归实现方式
public static int binarySearch(int[] param, int target) {
if (param.length == 0) {
return -1;
}
int middleIndex = param.length / 2;
int middleValue = param[middleIndex];
if (target == middleValue) {
return target;
}
while (target != middleValue && target < middleValue) {
int[] leftParam = Arrays.copyOfRange(param, 0, middleIndex);
int result = binarySearch(leftParam, target);
if (result == target) {
return result;
}else {
return -1;
}
}
while (target != middleValue && target > middleValue) {
int[] rightParam = Arrays.copyOfRange(param, middleIndex + 1, param.length);
int result = binarySearch(rightParam, target);
if (result == target) {
return result;
}else {
return -1;
}
}
return -1;
}
迭代实现方式
public static int binarySearch(int[] param, int target) {
if (param.length == 0) {
return -1;
}
int left = 0;
int right = param.length-1;
while (left<=right){
int middle = left +(right-left)/2;
if(target == param[middle]){
return middle;
}else if(target<param[middle]){
right = middle-1;
}else if(target>param[middle]){
left = middle+1;
}
}
return -1;
}
二者的不同在于，递归方式每次切割一半的数组作为入参，从而缩小查找范围
迭代方式改变索引搜索区间，每次左边索引移动，或者右边索引移动一个位置，缩小查询的区间范围
迭代法实现二分查找看似简单，但细节很难把握，容易陷进坑里。到底是“<=” 还是“<” ,到底是arrays.length 还是arrays.length-1? 很容易搞晕。正如发明 KMP 算法的Knuth大佬说的：Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...思维简单很简单，细节很磨人
下边就抽丝剥茧，给你捋清楚：
1 while (left<=right) 处到底应该是left<=right还是left<right呢？首先要明白，<= 就等价于[1,2,3] 闭合区间，而< 就等价于[1,2,3）就是左闭右开的区间。所以首先搞清楚最后一位是否包闭合
2 right的值应该是param.length-1，还是param.length，决定了是否闭合 如果right=param.length 那么就应该是开区间，否则会索引越界，反之，如果right=param.length-1 那么while中就是闭区间，包含等号。即满足这一条件的时候，还会进入while方法体，继续执行
3 为什么是left = mid+1; 因为while中的条件是闭合区间，所以本次搜索已经验证过mid位置处的值是否满足，所以右半边数组的起始索引就从下一位，即mid+1位置开始搜索。反之，如果搜索左半边数组，就从上一位，mid-1位置，搜索左半边位置，即right=mid-1;
4看完以后思路应该清晰了，但你会发现这个方法其实有很大的局限性，使用范围有限。比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。
这样的需求很常见。常见的思路可能会想，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以，但不是很好，脱离了二分查找的精髓了，因为这样难以保证二分查找对数级的复杂度了。
接下来通过一个案例所展示的技巧解决这个问题，让这个算法具有真正的实用价值。跟着我来一起学习吧。
下边是寻找左边界的代码
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = (left + right) / 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为什么 while(left < right) 而不是 <= ?
解答：这个问题应该不难回答了吧，因为right = nums.length 也就是索引越界的位置，所以应该是<左闭右开的区间形式，不包含最后一位
2 while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 恰巧为空，所以可以正确终止，不再进入循环体中
3为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？这个需要一步步来，尤其要理解“左边界”的特殊含义：
left_bound.png
nums数组中小于target=2的元素有1个
比如对于有序数组 nums = [3,4,5,6], target = 2，算法会返回 0，含义是：nums 中小于 2 的元素有 0 个。如果 target = 9，算法会返回 4，含义是：nums 中小于 8 的元素有 4 个
结合以上分析可以看出：返回的值（即left左边界值）取值是闭区间[0,nums.length],所以我们简单添加两行代码就能在正确的时候 return -1：
nums[left] == target? left：-1
4 left =mid+1,right=mid 这还是符合我们之前说的，左边界右移，右边界左移
5 为什么该算法能够搜索左侧边界？
是下边这段代码
if (nums[mid] == target)
right = mid;
这段代码的意思就是将右边界不断替换为最新的mid值，而mid值是不断减小的，在[left,mid) 位置上继续搜索，这一点确实不容易想到，也是技巧所在了
网友评论