也是利用二分的upper法实现的，不知道什么是upper？看这里 -> 二分查找法upper版（找大于某个值的最小下标）递归+非递归版 - 翰林猿 - 博客园 (cnblogs.com)
思路：
-
先利用upper找到上界的index
-
拿着index-1的下标（也就是重复值的最大下标）向前遍历，一直到遍历到发现不相等的元素即可。
package com.Search;
/**
* @Author: 翰林猿
* @Description: 查找目标元素最小的下标元素 lowerCeil
**/
public class BinarySearchCeil {
public BinarySearchCeil() {
}
public static <E extends Comparable<E>> int searchLowerCeil(E[] data, E target) {
return lowerCeil(data, target);
}
public static <E extends Comparable<E>> int searchUpper(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 <E extends Comparable<E>> int lowerCeil(E[] arr, E target) { //查找最小下标
int minIndex = 0;
int index = searchUpper(arr, 0, arr.length, target); //也是先用upper获取最大下标先
if (arr[index - 1].compareTo(target) == 0) { //如果最大下标-1等于目标值，说明其实是上界
minIndex = findMinIndex(arr, index - 1); //找到最小下标
}
return minIndex;
}
public static <E extends Comparable<E>> int findMinIndex(E[] arr, int index) {
int r = index;
while (arr[index] == arr[r]) { //不断向前遍历直到发现与target不同的元素下标
if (r == 0)
return 0;
else
r--;
}
return r + 1; //最后while循环过后的r是最小target的前一个下标，所以要+1，返回target最小的下标
}
public static void main(String[] args) {
Integer[] arr = {1, 1, 1, 2, 2, 3, 6, 6, 6 , 8, 18, 20};
int lowerCeil = searchLowerCeil(arr, 20);
System.out.println(lowerCeil);
}
}