(相关资料图)
需求：比如说查询一个班级大于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 > 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) { //如果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 > 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 < 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); } }