這篇文章主要介紹“Java二分查找方法如何使用”，在日常操作中，相信很多人在Java二分查找方法如何使用問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Java二分查找方法如何使用”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！
成都服務(wù)器托管，成都創(chuàng)新互聯(lián)提供包括服務(wù)器租用、BGP機(jī)房服務(wù)器托管、帶寬租用、云主機(jī)、機(jī)柜租用、主機(jī)租用托管、CDN網(wǎng)站加速、申請(qǐng)域名等業(yè)務(wù)的一體化完整服務(wù)。電話咨詢：18982081108
功能:排行榜
需求:按積分給前端返回一個(gè)有序集合，為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)。
能解決問題那二分查找哪來(lái)的？
第一:indexOf底層的遍歷如果極端情況下，10000用戶，恰好當(dāng)前用戶排在第10000個(gè)，那效率太低。
方案二 二分查找 Collections.binarySearch
Tuning parameters for algorithms 優(yōu)化算法 public static int binarySearch(List> list, T key) { if (list instanceof RandomAccess || list.size()
閾值為5000
private static final int BINARYSEARCH_THRESHOLD = 5000;
二分查找源代碼
private static int indexedBinarySearch(List> list, T key) { int low = 0; int high = list.size()-1;
while (low <= high) { int mid = (low + high) >>> 1; Comparable 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 }
如何測(cè)試效率？集合中放10萬(wàn)數(shù)據(jù)去測(cè)試下indexOf和binarySearch即可
public static void main(String[] args) { List 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)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！
標(biāo)題名稱：Java二分查找方法如何使用
標(biāo)題URL：
http://weahome.cn/article/psphhp.html
重慶分公司
重慶分公司
