我就是想找个下标，怎么用到二分查找了？
功能:排行榜
需求:按积分给前端返回一个有序集合，为0不显示，并给出当前用户排名位置
实现:
- 计算出所有用户(包含当前用户的)积分集合
- 过滤掉为0的，且按分数倒序排列，分数越高排名越前
- 再把当前用户信息找到，判断其在集合中的位置
方案一:List.indexOf(object)
源码
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
list不包含返回-1
return -1;
}底层就是遍历判断元素相当则返回元素位置，下标从0开始，所以结果需要+1。
当前方案不能解决问题吗？
能,通过逻辑判断可不用contains判断是否在集合内。
能解决问题那二分查找哪来的？
第一:indexOf底层的遍历如果极端情况下，10000用户，恰好当前用户排在第10000个，那效率太低。
方案二 二分查找 Collections.binarySearch
Tuning parameters for algorithms
优化算法
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}阈值为5000
private static final int BINARYSEARCH_THRESHOLD = 5000;二分查找源代码
private static <T>
int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
int low = 0;
int high = list.size()-1;
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = list.get(mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}如何测试效率？集合中放10万数据去测试下indexOf和binarySearch即可
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list.add(i);
}
long time = System.currentTimeMillis();
list.indexOf(58645);
System.out.println("indexOf耗时:");
System.out.println(System.currentTimeMillis()-time);
long binarySearchtime = System.currentTimeMillis();
Collections.binarySearch(list,58645);
System.out.println("二分查找耗时:");
System.out.println(System.currentTimeMillis()-binarySearchtime);
}
indexOf耗时:
13
二分查找耗时:
1性能提升13倍
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-08-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读