折半查找

問題描述：給定一個整數(shù)X和整數(shù)A0，A1，A2……A(n-1)，后者已經(jīng)預(yù)先排序并在內(nèi)存中，求下標(biāo)i使得Ai = X ，如果X不在數(shù)據(jù)中，則返回i = -1。

---

我們首先可以想到的一種方法就是從左到右遍歷，逐個匹配，運(yùn)行花費(fèi)線性時間。然而，這樣的算法并沒有考慮到題目中已經(jīng)排序的這個事實(shí)，所以這種算法不能算是最優(yōu)解。那么這里就引入了我們的折半查找，每次驗(yàn)證X是否是居中元素，如果是，即為找到；如果X小于居中元素，檢查左側(cè)部分；如果X大于居中元素，檢查右側(cè)部分。

public class BinarySearch {public static void main(String[] args) {String[] str = {"a","b","c","1","2","3"};System.out.println(binarySearch(str , "b"));}public static <String extends Comparable <? super String>> int binarySearch(String[] a,String x){int low = 0;int high = a.length -1;while (low <= high){int mid = (low + high) / 2;if(a[mid].compareTo(x) < 0){low = mid + 1;}else if(a[mid].compareTo(x) > 0){high = mid -1;}else {return mid;}}return -1;}}

其中難以理解的地方就是

總結(jié)

以上是生活随笔為你收集整理的查找算法——折半查找（JAVA）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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