二分查找是一種查詢效率非常高的查找算法。又稱折半查找。起初在數據結構中學習遞歸時實現二分查找，實際上不用遞歸也可以實現，畢竟遞歸是需要開辟額外的空間的來 輔助查詢。本文就介紹兩種方法二分查找算法思想有序的序列，每次都是以序列的中間位置的數來與待查找的關鍵字進行比較，每次縮小一半的查找范圍， 直到匹配成功。一個情景：將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄 將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查 找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。二分查找優缺點1. 優點是比較次數少，查找速度快，平均性能好；2. 缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。使用條件：查找序列是順序結構，有序。 java代碼實現使用遞歸實現public class Test{/*** 使用遞歸的二分查找* @param arr 有序數組* @param key 待查找的關鍵字* @param low* @param high* @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;} }public static void main(String[] args) {int[] arr = {1,2,3,4,5,8,9,10};int index = Test.recursionBinarySearch(arr, 2, 1, 5);System.out.println(index);}} 不使用遞歸實現（while循環）/*** 不使用遞歸的二分查找* @param arr* @param key* @return*/public static int commonBinarySearch(int[] arr,int key) {int low = 0;int high = arr.length - 1;// 定義middleint middle = 0;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;}}// 最后仍然沒有找到,則返回-1return -1;} public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int key = 4;int position = commonBinarySearch(arr, key);if(position == -1) {System.out.println("查找的是"+key+",序列中沒有該數!"); }else {System.out.println("查找的是"+key+",找到的位置為: " + position);}}

?

總結

以上是生活随笔為你收集整理的java实现二分查找-两种方式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。