需求
思路与二分法基本相同，只不过是对比的逻辑发生了一些小变化，这里所说的上界就是指大于某个值的最小下标。
-
当mid
-
当mid > target：说明 mid 有可能是target的上界，所以我们加个判断，如果mid前一个元素就刚好是target，说明mid就是我们要找的上界，否则继续找。
另一个注意的点，就是我们取变量 r 的时候，不再是取数组最大的下标了，而是要超过一个，因为如果你找的是数组最后一个元素的上界，其实是不在数组里的。
递归版：
package com.Search;
/**
* @Author: 翰林猿
* @Description: 二分查找upper版（找大于某个值的最小下标）
**/
public class BinarySearchUpper {
public BinarySearchUpper() {
}
public static > int SearchUpper(E[] data, E target) {
return SearchUpper(data, 0, data.length, target); //是length而不是length-1，因为有可能上界值不在该数组里，所以此时r就应该取大于数组最大值下标+1的位置
}
/**
* @Description 递归版本
*/
public static > 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 && 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 > int SearchUpper2(E[] data, E target) {
return SearchUpper2(data, 0, data.length, target); //是length而不是length-1，因为有可能上界值不在该数组里，所以此时r就应该取大于数组最大值下标+1的位置
}
/**
* @Description 非递归版本
*/
public static > int SearchUpper2(E[] data, int l, int r, E target) {
while (l 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);
}
}服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: 迎向浪潮之巅，GOTC 2023 数据与数据库技术专题论坛即将召开
全球开源技术峰会（Global Open-source Technology Conference，简称 GOTC）是由开放原子开源基金会、上海浦东软件园、 Linux 基金会亚太区和开源中国联合发起的，面向全球开发者的一场盛大开源技术盛宴。 GOTC 202…
