您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java二分查找方法如何使用”,在日常操作中,相信很多人在Java二分查找方法如何使用問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”Java二分查找方法如何使用”的疑惑有所幫助!接下來,請跟著小編一起來學(xué)習(xí)吧!
功能:排行榜
需求:按積分給前端返回一個有序集合,為0不顯示,并給出當(dāng)前用戶排名位置
實(shí)現(xiàn):
計(jì)算出所有用戶(包含當(dāng)前用戶的)積分集合
過濾掉為0的,且按分?jǐn)?shù)倒序排列,分?jǐn)?shù)越高排名越前
再把當(dāng)前用戶信息找到,判斷其在集合中的位置
方案一: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; }
底層就是遍歷判斷元素相當(dāng)則返回元素位置,下標(biāo)從0開始,所以結(jié)果需要+1。
當(dāng)前方案不能解決問題嗎?
能,通過邏輯判斷可不用contains判斷是否在集合內(nèi)。
能解決問題那二分查找哪來的?
第一:indexOf底層的遍歷如果極端情況下,10000用戶,恰好當(dāng)前用戶排在第10000個,那效率太低。
方案二 二分查找 Collections.binarySearch
Tuning parameters for algorithms 優(yōu)化算法 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萬數(shù)據(jù)去測試下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耗時(shí):");
System.out.println(System.currentTimeMillis()-time);
long binarySearchtime = System.currentTimeMillis();
Collections.binarySearch(list,58645);
System.out.println("二分查找耗時(shí):");
System.out.println(System.currentTimeMillis()-binarySearchtime);
}
indexOf耗時(shí):
13
二分查找耗時(shí):
1
性能提升13倍
到此,關(guān)于“Java二分查找方法如何使用”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識,請繼續(xù)關(guān)注億速云網(wǎng)站,小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。