兩種java實現二分查找的方式
起初在數據結構中學習遞歸時實現二分查找，實際上不用遞歸也可以實現，畢竟遞歸是需要開辟額外的空間的來輔助查詢。本文就介紹兩種方法
1、二分查找算法思想
有序的序列，每次都是以序列的中間位置的數來與待查找的關鍵字進行比較，每次縮小一半的查找范圍，直到匹配成功。
一個情景：將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
2、二分查找圖示說明
圖片來源百度圖片：
3、二分查找優缺點
優點：
比較次數少，查找速度快，平均性能好；
缺點:
是要求待查表為有序表，且插入刪除困難。
因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件：
查找序列是順序結構，有序。
3、java代碼實現
3.1 使用遞歸實現
/**
* 使用遞歸的二分查找
*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;
}
}
3.1 不使用遞歸實現（while循環）
/**
* 不使用遞歸的二分查找
*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
}
3.3 測試
測試代碼：
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,序列中沒有該數！
4、時間復雜度
采用的是分治策略
最壞的情況下兩種方式時間復雜度一樣：O(log2 N)
最好情況下為O（1）
5、空間復雜度
算法的空間復雜度並不是計算實際占用的空間，而是計算整個算法的輔助空間單元的個數
非遞歸方式：
由於輔助空間是常數級別的所以：空間復雜度是O(1);
遞歸方式：遞歸的次數和深度都是log2 N,每次所需要的輔助空間都是常數級別的：
空間復雜度：O(log2N )
到此這篇關於兩種java實現二分查找的方式的文章就介紹到這瞭,更多相關java實現二分查找內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！