526互联

二分查找法ceil版（找某个重复值的最大下标）利用二分upper法实现

发布时间 2023-06-22 14:09:46作者: 翰林猿

  • 如果有等于target的元素就返回最大的下标元素。

package com.Search;
​
/**
 * @Author: 翰林猿
 * @Description: 查找目标元素最大的下标元素 ceil
 **/
public class BinarySearchCeil {
    public BinarySearchCeil() {
    }
    public static <E extends Comparable<E>> int searchCeil(E[] data, E target) {
        return ceil(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 ceil(E[] arr, E target) {
        int index = searchUpper(arr, 0,arr.length,target);
        if(arr[index - 1].compareTo(target) == 0) {
            return index - 1;
        }
        return index;
    }
​
​
    public static void main (String[]args){
        Integer[] arr = {1, 1,1, 2, 2, 3, 6, 8, 18, 20};
        int ceilIndex = searchCeil(arr, 1);
        System.out.println(ceilIndex);
    }
}