二分查找法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);         }     }