<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
起初在資料結構中學習遞迴時實現二分查詢,實際上不用遞迴也可以實現,畢竟遞迴是需要開闢額外的空間的來輔助查詢。本文就介紹兩種方法
有序的序列,每次都是以序列的中間位置的數來與待查詢的關鍵字進行比較,每次縮小一半的查詢範圍,直到匹配成功。
一個情景:將表中間位置記錄的關鍵字與查詢關鍵字比較,如果兩者相等,則查詢成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查詢關鍵字,則進一步查詢前一子表,否則進一步查詢後一子表。重複以上過程,直到找到滿足條件的記錄,使查詢成功,或直到子表不存在為止,此時查詢不成功。
圖片來源百度圖片:
優點:
比較次數少,查詢速度快,平均效能好;
缺點:
是要求待查表為有序表,且插入刪除困難。
因此,折半查詢方法適用於不經常變動而查詢頻繁的有序列表。
使用條件:
查詢序列是順序結構,有序。
/** * 使用遞迴的二分查詢 *title:recursionBinarySearch *@param arr 有序陣列 *@param key 待查詢關鍵字 *@return 找到的位置 */ public static int recursionBinarySearch(int[] arr,int key,int low,int high){ if(key < arr[low] || key > arr[high] || low > high){ return -1; } int middle = (low + high) / 2; //初始中間位置 if(arr[middle] > key){ //比關鍵字大則關鍵字在左區域 return recursionBinarySearch(arr, key, low, middle - 1); }else if(arr[middle] < key){ //比關鍵字小則關鍵字在右區域 return recursionBinarySearch(arr, key, middle + 1, high); }else { return middle; } }
/** * 不使用遞迴的二分查詢 *title:commonBinarySearch *@param arr *@param key *@return 關鍵字位置 */ public static int commonBinarySearch(int[] arr,int key){ int low = 0; int high = arr.length - 1; int middle = 0; //定義middle if(key < arr[low] || key > arr[high] || low > high){ return -1; } while(low <= high){ middle = (low + high) / 2; if(arr[middle] > key){ //比關鍵字大則關鍵字在左區域 high = middle - 1; }else if(arr[middle] < key){ //比關鍵字小則關鍵字在右區域 low = middle + 1; }else{ return middle; } } return -1; //最後仍然沒有找到,則返回-1 }
測試程式碼:
public static void main(String[] args) { int[] arr = {1,3,5,7,9,11}; int key = 4; //int position = recursionBinarySearch(arr,key,0,arr.length - 1); int position = commonBinarySearch(arr, key); if(position == -1){ System.out.println("查詢的是"+key+",序列中沒有該數!"); }else{ System.out.println("查詢的是"+key+",找到位置為:"+position); } }
recursionBinarySearch()
的測試:key分別為0,9,10,15的查詢結果
查詢的是0,序列中沒有該數!
查詢的是9,找到位置為:4
查詢的是10,序列中沒有該數!
查詢的是15,序列中沒有該數!
commonBinarySearch()
的測試:key分別為-1,5,6,20的查詢結果
查詢的是-1,序列中沒有該數!
查詢的是5,找到位置為:2
查詢的是6,序列中沒有該數!
查詢的是20,序列中沒有該數!
採用的是分治策略
最壞的情況下兩種方式時間複雜度一樣:O(log2 N)
最好情況下為O(1)
演演算法的空間複雜度並不是計算實際佔用的空間,而是計算整個演演算法的輔助空間單元的個數
非遞迴方式:
由於輔助空間是常數級別的所以:空間複雜度是O(1);
遞迴方式:遞迴的次數和深度都是log2 N,每次所需要的輔助空間都是常數級別的:
空間複雜度:O(log2N )
到此這篇關於兩種java實現二分查詢的方式的文章就介紹到這了,更多相關java實現二分查詢內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!
相關文章
<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
综合看Anker超能充系列的性价比很高,并且与不仅和iPhone12/苹果<em>Mac</em>Book很配,而且适合多设备充电需求的日常使用或差旅场景,不管是安卓还是Switch同样也能用得上它,希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
除了L4WUDU与吴亦凡已经多次共事,成为了明面上的厂牌成员,吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节,这也是20XXCLUB首次全员合照,王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
目前应用IPFS的机构:1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆,历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
开拓者的车机是兼容苹果和<em>安卓</em>,虽然我不怎么用,但确实兼顾了我家人的很多需求:副驾的门板还配有解锁开关,有的时候老婆开车,下车的时候偶尔会忘记解锁,我在副驾驶可以自己开门:第二排设计很好,不仅配置了一个很大的
2021-06-01 09:30:48
不仅是<em>安卓</em>手机,苹果手机的降价力度也是前所未有了,iPhone12也“跳水价”了,发布价是6799元,如今已经跌至5308元,降价幅度超过1400元,最新定价确认了。iPhone12是苹果首款5G手机,同时也是全球首款5nm芯片的智能机,它
2021-06-01 09:30:45