Class SearchUtil
java.lang.Object
com.sure.tool.util.SearchUtil
有序数组/列表查找工具:上下界、范围查询、二分、插值与指数查找。
Guava / Hutool 均未提供 lowerBound / upperBound / range;本类补齐并保证 逆序比较器、重复元素、空集合与越界场景的行为确定性。
-
Method Summary
Modifier and TypeMethodDescriptionstatic <T> intbinarySearch(List<? extends T> list, T key, Comparator<? super T> cmp) 二分查找:语义与Collections.binarySearch(List, T)一致(命中返回下标, 未命中返回-(insertionPoint) - 1),额外支持空列表与nullkey 返回 -1。static intexponentialSearch(long[] sorted, long key) 指数查找:先指数步进缩小区间,再二分定位;命中返回下标,否则返回 -1。static intinterpolationSearch(long[] sorted, long key) 插值查找(适用于近似均匀分布的升序数组);命中返回下标,否则返回 -1。static <T extends Comparable<? super T>>
intlowerBound(List<? extends T> list, T key) 第一个不小于 key 的下标(插入点下界)。static <T> intlowerBound(List<? extends T> list, T key, Comparator<? super T> cmp) 按比较器求第一个不小于 key 的下标。static <T extends Comparable<? super T>>
List<T> 范围查询:返回下标[lowerBound(from), lowerBound(to))的不可变子列表。static <T extends Comparable<? super T>>
intupperBound(List<? extends T> list, T key) 第一个大于 key 的下标(插入点上界)。static <T> intupperBound(List<? extends T> list, T key, Comparator<? super T> cmp) 按比较器求第一个大于 key 的下标。
-
Method Details
-
lowerBound
第一个不小于 key 的下标(插入点下界)。全部元素小于 key 时返回list.size()。- Type Parameters:
T- 元素类型- Parameters:
list- 升序列表key- 查找键- Returns:
- 插入点下标
-
upperBound
第一个大于 key 的下标(插入点上界)。全部元素不大于 key 时返回list.size()。- Type Parameters:
T- 元素类型- Parameters:
list- 升序列表key- 查找键- Returns:
- 插入点下标
-
lowerBound
按比较器求第一个不小于 key 的下标。- Type Parameters:
T- 元素类型- Parameters:
list- 按比较器有序的列表key- 查找键cmp- 比较器- Returns:
- 插入点下标
-
upperBound
按比较器求第一个大于 key 的下标。- Type Parameters:
T- 元素类型- Parameters:
list- 按比较器有序的列表key- 查找键cmp- 比较器- Returns:
- 插入点下标
-
range
范围查询:返回下标[lowerBound(from), lowerBound(to))的不可变子列表。- Type Parameters:
T- 元素类型- Parameters:
list- 升序列表from- 区间下界(含)to- 区间上界(不含)- Returns:
- 不可变子列表
-
binarySearch
二分查找:语义与Collections.binarySearch(List, T)一致(命中返回下标, 未命中返回-(insertionPoint) - 1),额外支持空列表与nullkey 返回 -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
-