二分查找法upper版（找大于某个值的最小下标）递归+非递归版
需求：比如说查询一个班级大于60分的最低分等等。
思路与二分法基本相同，只不过是对比的逻辑发生了一些小变化，这里所说的上界就是指大于某个值的最小下标。
当mid < target ：说明 target 的上界还在mid的右边，所以要去找比mid大的
当mid > target：说明 mid 有可能是target的上界，所以我们加个判断，如果mid前一个元素就刚好是target，说明mid就是我们要找的上界，否则继续找。
另一个注意的点，就是我们取变量 r 的时候，不再是取数组最大的下标了，而是要超过一个，因为如果你找的是数组最后一个元素的上界，其实是不在数组里的。
递归版：
package com.Search;
/**
* @Author: 翰林猿
* @Description: 二分查找upper版（找大于某个值的最小下标）
**/
public class BinarySearchUpper {
public BinarySearchUpper() {
}
public static <E extends Comparable<E>> int SearchUpper(E[] data, E target) {
return SearchUpper(data, 0, data.length, target); //是length而不是length-1，因为有可能上界值不在该数组里，所以此时r就应该取大于数组最大值下标+1的位置
}
/**
* @Description 递归版本
*/
public static <E extends Comparable<E>> int SearchUpper(E[] data, int l, int r, E target) {
if (l >= r) return -1;
int mid = l + (r - l) / 2;
if (data[mid].compareTo(target) <= 0) { //如果mid小于目标值，说明target的上界还在右边，要去找比mid大的
return SearchUpper(data, mid + 1, r, target);
}
if (data[mid].compareTo(target) > 0 && data[mid - 1].compareTo(target) == 0) {
return mid;
}
//说明mid又大于target，但是mid-1又不等于target，说明当前的mid不是上界。比如说测试用例1, 1, 1, 2, 2, 3, 6, 8, 18, 20
//我们要找大于3的最小下标也就是6的下标，但是经过两次递归，mid=18，但是18所在的下标为8，8-1=7的元素是8，但是8并不等于3，所以mid=18时不是我们要找的upper
//此时继续递归
return SearchUpper(data, l, mid, target); //mid已经大于目标值了，而且当前的mid不是上界，所以我们往左边找
}
public static void main (String[]args){
Integer[] arr = {1, 1,1, 2, 2, 3, 6, 8, 18, 20};
int index = SearchUpper(arr, 3);
System.out.println(index);
}
}非递归版：
package com.Search;
/**
* @Author: 翰林猿
* @Description: 二分查找upper版（找大于某个值的最小下标）
**/
public class BinarySearchUpper {
public BinarySearchUpper() {
}
public static <E extends Comparable<E>> int SearchUpper2(E[] data, E target) {
return SearchUpper2(data, 0, data.length, target); //是length而不是length-1，因为有可能上界值不在该数组里，所以此时r就应该取大于数组最大值下标+1的位置
}
/**
* @Description 非递归版本
*/
public static <E extends Comparable<E>> int SearchUpper2(E[] data, int l, int r, E target) {
while (l < r) {
int mid = l + (r - l) / 2;
if (data[mid].compareTo(target) == 0) {
return mid + 1;
} else if (data[mid].compareTo(target) > 0) { // 这个r = mid是因为mid的位置可能是目标值
r = mid;
} else {
l = mid + 1;
}
}
// l和r最后都都指向同一个位置。没找到则返回arr.length
return l;
}
public static void main (String[]args){
Integer[] arr = {1, 1,1, 2, 2, 3, 6, 8, 18, 20};
int index2 = SearchUpper2(arr, 3);
System.out.println(index2);
}
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章