起初在數(shù)據(jù)結(jié)構(gòu)中學(xué)習(xí)遞歸時(shí)實(shí)現(xiàn)二分查找，實(shí)際上不用遞歸也可以實(shí)現(xiàn)，畢竟遞歸是需要開(kāi)辟額外的空間的來(lái)輔助查詢。本文就介紹兩種方法

1、二分查找算法思想

有序的序列，每次都是以序列的中間位置的數(shù)來(lái)與待查找的關(guān)鍵字進(jìn)行比較，每次縮小一半的查找范圍，直到匹配成功。

一個(gè)情景：將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過(guò)程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

2、二分查找圖示說(shuō)明

圖片來(lái)源百度圖片：

3、二分查找優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

比較次數(shù)少，查找速度快，平均性能好；

缺點(diǎn):

是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。

使用條件：

查找序列是順序結(jié)構(gòu)，有序。

3、java代碼實(shí)現(xiàn)

3.1 使用遞歸實(shí)現(xiàn)

/**
* 使用遞歸的二分查找
*title:recursionBinarySearch
*@param arr 有序數(shù)組
*@param key 待查找關(guān)鍵字
*@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){
 //比關(guān)鍵字大則關(guān)鍵字在左區(qū)域
 return recursionBinarySearch(arr, key, low, middle - 1);
}else if(arr[middle] < key){
 //比關(guān)鍵字小則關(guān)鍵字在右區(qū)域
 return recursionBinarySearch(arr, key, middle + 1, high);
}else {
 return middle;
} 

}

3.1 不使用遞歸實(shí)現(xiàn)（while循環(huán)）

/**
* 不使用遞歸的二分查找
*title:commonBinarySearch
*@param arr
*@param key
*@return 關(guān)鍵字位置
*/
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){
  //比關(guān)鍵字大則關(guān)鍵字在左區(qū)域
  high = middle - 1;
 }else if(arr[middle] < key){
  //比關(guān)鍵字小則關(guān)鍵字在右區(qū)域
  low = middle + 1;
 }else{
  return middle;
 }
}

return -1;  //最后仍然沒(méi)有找到，則返回-1
}

3.3 測(cè)試

測(cè)試代碼：

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+",序列中沒(méi)有該數(shù)！");
}else{
 System.out.println("查找的是"+key+",找到位置為："+position);
}

}

recursionBinarySearch()的測(cè)試：key分別為0，9，10，15的查找結(jié)果

查找的是0,序列中沒(méi)有該數(shù)！

查找的是9,找到位置為：4

查找的是10,序列中沒(méi)有該數(shù)！

查找的是15,序列中沒(méi)有該數(shù)！

commonBinarySearch()的測(cè)試：key分別為-1，5，6，20的查找結(jié)果

查找的是-1,序列中沒(méi)有該數(shù)！

查找的是5,找到位置為：2

查找的是6,序列中沒(méi)有該數(shù)！

查找的是20,序列中沒(méi)有該數(shù)！

4、時(shí)間復(fù)雜度

采用的是分治策略

最壞的情況下兩種方式時(shí)間復(fù)雜度一樣：O(log2 N)

最好情況下為O（1）

5、空間復(fù)雜度

算法的空間復(fù)雜度并不是計(jì)算實(shí)際占用的空間，而是計(jì)算整個(gè)算法的輔助空間單元的個(gè)數(shù)

非遞歸方式：
由于輔助空間是常數(shù)級(jí)別的所以：空間復(fù)雜度是O(1);

遞歸方式：遞歸的次數(shù)和深度都是log2 N,每次所需要的輔助空間都是常數(shù)級(jí)別的：

空間復(fù)雜度：O(log2N )

到此這篇關(guān)于兩種java實(shí)現(xiàn)二分查找的方式的文章就介紹到這了,更多相關(guān)java實(shí)現(xiàn)二分查找內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！

原文鏈接：https://blog.csdn.net/maoyuanming0806/article/details/78176957