二分查找的條件是對(duì)一組有序數(shù)組的查找，這一點(diǎn)很容易忘記，在使用二分查找的時(shí)候先要對(duì)數(shù)組進(jìn)行排序。

先說(shuō)一下二分查找的思路：一個(gè)有序數(shù)組，想要查找一個(gè)數(shù)字key的下標(biāo)，首先算出中間下標(biāo)mid，利用mid把這個(gè)數(shù)組分為兩半，前一半從下標(biāo)0到mid-1，后一半從mid+1到數(shù)組最后一個(gè)元素（下標(biāo)是數(shù)組長(zhǎng)度減一）。把這個(gè)查找的元素key和數(shù)組下標(biāo)為mid的元素進(jìn)行比較，也就是和中間那個(gè)元素進(jìn)行比較，如果比這個(gè)元素的小那么把查找范圍縮小到原數(shù)組的前一半（把查找下標(biāo)縮短到0到mid-1），如果比中間mid下標(biāo)元素大那么范圍就是后半部分（下標(biāo)為mid+1到數(shù)組長(zhǎng)度減一），這樣來(lái)回反復(fù)取中間比較最后就會(huì)定位到要查找元素key的下標(biāo)。

二分查找有兩種實(shí)現(xiàn)方式：

非遞歸實(shí)現(xiàn)

遞歸實(shí)現(xiàn)

在jdk源碼中Arrays數(shù)組工具類中已經(jīng)封裝好了二分查找算法，不會(huì)寫可以看看源碼，源碼實(shí)現(xiàn)的方式肯定是效率比較高的。比如計(jì)算數(shù)組中間下標(biāo)mid利用移位運(yùn)算。

非遞歸實(shí)現(xiàn)：

/*** @param array 操作數(shù)組* @param key 查找元素* @return 元素下標(biāo)*/public static int binSearch(int[] array,int key){int start=0;int mid;int end=array.length-1;while(start<=end){mid=(end-start)/2+start;if(key<array[mid]){end=mid-1;}else if(key>array[mid]){start=mid+1;}else{return mid;}}return -1;}

?

?

遞歸實(shí)現(xiàn)：

/*** @param array 操作數(shù)組* @param key 查找元素* @param start 開始下標(biāo)* @param end 結(jié)束下標(biāo)* @return 元素下標(biāo)*/public static int binSearch1(int[] array,int key,int start,int end){int mid=(end-start)/2+start;if(key==array[mid]){return mid;}else if(start>=end){return -1;}else if(key>array[mid]){return binSearch1(array,key,mid+1,end);}else if(key<array[mid]){return binSearch1(array,key,start,mid-1);}return -1;}

?

總結(jié)

以上是生活随笔為你收集整理的二分查找算法的两种实现方式：非递归实现和递归实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。