溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“Java二分查找方法如何使用”，在日常操作中，相信很多人在Java二分查找方法如何使用問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java二分查找方法如何使用”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
功能:排行榜
需求:按積分給前端返回一個有序集合，為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;elsereturn 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倍
到此，關于“Java二分查找方法如何使用”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
