資訊專(zhuān)欄INFORMATION COLUMN
摘要：查找算法之二分查找法思想二分查找法的思想非常簡(jiǎn)單，對(duì)于一個(gè)有序數(shù)列，找它中間的元素，看是否是查找目標(biāo)，如果不是，就看這個(gè)查找目標(biāo)是小于還是大于中間元素，然后在對(duì)應(yīng)的區(qū)間內(nèi)重復(fù)上述過(guò)程。
查找算法之二分查找法 思想
二分查找法的思想非常簡(jiǎn)單，對(duì)于一個(gè)有序數(shù)列，找它中間的元素，看是否是查找目標(biāo)，如果不是，就看這個(gè)查找目標(biāo)是小于還是大于中間元素，然后在對(duì)應(yīng)的區(qū)間內(nèi)重復(fù)上述過(guò)程。
算法需要注意幾個(gè)問(wèn)題：
while 循環(huán)：while 循環(huán)的條件應(yīng)該是 left < right 還是 left <= right 呢？
這可以從我們?cè)O(shè)置的左右邊界判斷出來(lái)，我們?cè)O(shè)置的 left = 0, right = n - 1，因此 [left, right] 是一個(gè)閉區(qū)間，那么當(dāng) left = right 時(shí)，[left, right] 區(qū)間同樣滿足我們的設(shè)置，因此，這個(gè)循環(huán)內(nèi)應(yīng)該是 left <= right。
target 和 arr[mid] 的判斷：當(dāng) target > arr[mid] 時(shí)，是應(yīng)該 left = mid 還是 left = mid + 1 呢？
這和在 while 中的判斷是一個(gè)思路，當(dāng) target > arr[mid] 時(shí)，target 在 [mid + 1, r] 中，而非 [mid, r]，因?yàn)轱@然此時(shí) mid 已經(jīng)不可能等于 target 了，因此我們不需要再比較 target 和 arr[mid]。
同樣地，當(dāng) target < arr[mid] 時(shí)，也是類(lèi)似的判斷。
循環(huán)不變量：left 和 right 的定義十分重要，因?yàn)樵诤竺嫖覀円粩嗟鼐S護(hù)這個(gè)定義，我們必須要保證是在 [left, right] 這個(gè)區(qū)間里尋找 target，這也就是 循環(huán)不變量，意思就是 left 和 right 的值雖然一直在變化，但是有一個(gè)聲明 在 [left, right] 區(qū)間內(nèi)尋找 target 是永遠(yuǎn)不變的，只要我們維護(hù)住這個(gè) 循環(huán)不變量，那么就可以保證我們的算法是正確的。當(dāng)然，這里你也可以定義成 left = 0, right = n，即[left, right)，那么此時(shí)定義就發(fā)生了變化，相應(yīng)地，在 while 中為了維護(hù)這個(gè)定義，我們需要把條件改成 left < right，因?yàn)楫?dāng) left = right 時(shí)，顯然 [left, right)是錯(cuò)誤的，后面再查找時(shí)也要做相應(yīng)的修改。
private int binarySearch(T arr[], int n, T target) {
int left = 0, right = n - 1; // 在 [left, right] 區(qū)間內(nèi)尋找 target
while (left <= right) { // 當(dāng) left = right 時(shí)，區(qū)間 [left, right] 仍然有效
int mid = (left + right) / 2;
if (arr[mid] == target)
return mid;
if (target > arr[mid])
left = mid + 1; // target 在 [mid+1, r] 中
else
right = mid - 1; // target 在 [left, mid - 1] 中
}
return -1;
}
不知道到這里大家有沒(méi)有發(fā)現(xiàn)一個(gè) bug
因?yàn)?left 和 right 都是 int，所以當(dāng)值足夠大時(shí)，在計(jì)算 mid = (left + right) / 2 時(shí)可能會(huì)發(fā)生整型溢出！
因此，為了避免這個(gè)問(wèn)題，我們使用減法來(lái)計(jì)算。
完全正確的二分查找法
public int binarySearch(T[] arr, int n, T target) {
int left = 0, right = n - 1; // 在 [left, right] 區(qū)間內(nèi)尋找 target
while (left <= right) { // 當(dāng) left = right 時(shí)，區(qū)間 [left, right] 仍然有效
int mid = left + (right - left) / 2;
if (arr[mid].compareTo(target) == 0)
return mid;
if (target.compareTo(arr[mid]) > 0)
left = mid + 1; // target 在 [mid+1, r] 中
else
right = mid - 1; // target 在 [left, mid - 1] 中
}
return -1;
}
測(cè)試
我們可以寫(xiě)一個(gè) Util 來(lái)幫助我們生成測(cè)試用例
ArrayUtil.java
public static Integer[] generateSortedArray(int n) {
assert n > 0;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
return arr;
}
BinarySearch.java
public static void main(String[] args) {
BinarySearch bs = new BinarySearch();
int n = (int)Math.pow(10, 7); // 用 10,000,000 數(shù)據(jù)測(cè)試
Integer[] data = ArrayUtil.generateSortedArray(n);
long startTime = System.currentTimeMillis();
for (int i = 0; i < n; i++)
if (i != bs.binarySearch(data, n, i))
throw new IllegalStateException("find i failed");
long endTime = System.currentTimeMillis();
System.out.println("Binary Search success!");
System.out.println("Time cost: " + (endTime - startTime) + "ms");
}
完整代碼：github: My-Notes/algorithm（Java）/01-binarySearch/src/
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/69408.html
摘要：正文二分查找關(guān)于二分查找法二分查找法主要是解決在一堆數(shù)中找出指定的數(shù)這類(lèi)問(wèn)題。用二分查找法找尋上界與精確查找不同之處在于，精確查找分成三類(lèi)大于，小于，等于目標(biāo)數(shù)。 由一道題目引出的： 題目描述 給定一個(gè)有序的數(shù)組，查找某個(gè)數(shù)是否在數(shù)組中，請(qǐng)編程實(shí)現(xiàn)。 分析與解法 一看到數(shù)組本身已經(jīng)有序，我想你可能反應(yīng)出了要用二分查找，畢竟二分查找的適用條件就是有序的。那什么是二分查找呢？ 二分查找可以...
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹(shù)關(guān)于二叉樹(shù)，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹(shù)算法常見(jiàn)練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見(jiàn)數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹(shù)關(guān)于二叉樹(shù)，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹(shù)算法常見(jiàn)練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見(jiàn)數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹(shù)關(guān)于二叉樹(shù)，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹(shù)算法常見(jiàn)練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見(jiàn)數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...
摘要：測(cè)試用例輸入輸入輸入負(fù)數(shù)的輸入平方根為正整數(shù)的輸入平方根為小數(shù)的代碼實(shí)現(xiàn)寫(xiě)二分查找代碼需要注意的三點(diǎn)循環(huán)退出條件。使用二分查找之前，判斷問(wèn)題是否滿足二分查找的要求。 Time：2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿 題目：sqrt(x) Implement int sqrt(int x). Compute and retu...
閱讀 1873·2023-04-26 02:46
閱讀 2003·2021-11-25 09:43
閱讀 1147·2021-09-29 09:35
閱讀 2104·2019-08-30 15:56
閱讀 3426·2019-08-30 15:54
閱讀 2637·2019-08-29 16:35
閱讀 3124·2019-08-29 15:25
閱讀 3294·2019-08-29 14:01
