Class SearchUtil

java.lang.Object
com.sure.tool.util.SearchUtil

public final class SearchUtil extends Object
有序数组/列表查找工具:上下界、范围查询、二分、插值与指数查找。

Guava / Hutool 均未提供 lowerBound / upperBound / range;本类补齐并保证 逆序比较器、重复元素、空集合与越界场景的行为确定性。

  • Method Summary

    Modifier and Type
    Method
    Description
    static <T> int
    binarySearch(List<? extends T> list, T key, Comparator<? super T> cmp)
    二分查找:语义与 Collections.binarySearch(List, T) 一致(命中返回下标, 未命中返回 -(insertionPoint) - 1),额外支持空列表与 null key 返回 -1。
    static int
    exponentialSearch(long[] sorted, long key)
    指数查找:先指数步进缩小区间,再二分定位;命中返回下标,否则返回 -1。
    static int
    interpolationSearch(long[] sorted, long key)
    插值查找(适用于近似均匀分布的升序数组);命中返回下标,否则返回 -1。
    static <T extends Comparable<? super T>>
    int
    lowerBound(List<? extends T> list, T key)
    第一个不小于 key 的下标(插入点下界)。
    static <T> int
    lowerBound(List<? extends T> list, T key, Comparator<? super T> cmp)
    按比较器求第一个不小于 key 的下标。
    static <T extends Comparable<? super T>>
    List<T>
    range(List<? extends T> list, T from, T to)
    范围查询:返回下标 [lowerBound(from), lowerBound(to)) 的不可变子列表。
    static <T extends Comparable<? super T>>
    int
    upperBound(List<? extends T> list, T key)
    第一个大于 key 的下标(插入点上界)。
    static <T> int
    upperBound(List<? extends T> list, T key, Comparator<? super T> cmp)
    按比较器求第一个大于 key 的下标。

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Method Details

    • lowerBound

      public static <T extends Comparable<? super T>> int lowerBound(List<? extends T> list, T key)
      第一个不小于 key 的下标(插入点下界)。全部元素小于 key 时返回 list.size()。
      Type Parameters:
      T - 元素类型
      Parameters:
      list - 升序列表
      key - 查找键
      Returns:
      插入点下标
    • upperBound

      public static <T extends Comparable<? super T>> int upperBound(List<? extends T> list, T key)
      第一个大于 key 的下标(插入点上界)。全部元素不大于 key 时返回 list.size()。
      Type Parameters:
      T - 元素类型
      Parameters:
      list - 升序列表
      key - 查找键
      Returns:
      插入点下标
    • lowerBound

      public static <T> int lowerBound(List<? extends T> list, T key, Comparator<? super T> cmp)
      按比较器求第一个不小于 key 的下标。
      Type Parameters:
      T - 元素类型
      Parameters:
      list - 按比较器有序的列表
      key - 查找键
      cmp - 比较器
      Returns:
      插入点下标
    • upperBound

      public static <T> int upperBound(List<? extends T> list, T key, Comparator<? super T> cmp)
      按比较器求第一个大于 key 的下标。
      Type Parameters:
      T - 元素类型
      Parameters:
      list - 按比较器有序的列表
      key - 查找键
      cmp - 比较器
      Returns:
      插入点下标
    • range

      public static <T extends Comparable<? super T>> List<T> range(List<? extends T> list, T from, T to)
      范围查询:返回下标 [lowerBound(from), lowerBound(to)) 的不可变子列表。
      Type Parameters:
      T - 元素类型
      Parameters:
      list - 升序列表
      from - 区间下界(含)
      to - 区间上界(不含)
      Returns:
      不可变子列表
    • binarySearch

      public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> cmp)
      二分查找:语义与 Collections.binarySearch(List, T) 一致(命中返回下标, 未命中返回 -(insertionPoint) - 1),额外支持空列表与 null key 返回 -1。
      Type Parameters:
      T - 元素类型
      Parameters:
      list - 按比较器有序的列表
      key - 查找键
      cmp - 比较器
      Returns:
      命中下标或 -(insertionPoint) - 1;空列表 / null key 返回 -1
    • interpolationSearch

      public static int interpolationSearch(long[] sorted, long key)
      插值查找(适用于近似均匀分布的升序数组);命中返回下标,否则返回 -1。
      Parameters:
      sorted - 升序数组
      key - 查找键
      Returns:
      命中下标或 -1
    • exponentialSearch

      public static int exponentialSearch(long[] sorted, long key)
      指数查找:先指数步进缩小区间,再二分定位;命中返回下标,否则返回 -1。
      Parameters:
      sorted - 升序数组
      key - 查找键
      Returns:
      命中下标或 -1