摘要:查找算法之二分查找法思想二分查找法的思想非常簡單,對于一個有序數列,找它中間的元素,看是否是查找目標,如果不是,就看這個查找目標是小于還是大于中間元素,然后在對應的區間內重復上述過程。
查找算法之二分查找法 思想
二分查找法的思想非常簡單,對于一個有序數列,找它中間的元素,看是否是查找目標,如果不是,就看這個查找目標是小于還是大于中間元素,然后在對應的區間內重復上述過程。
算法需要注意幾個問題:
while 循環:while 循環的條件應該是 left < right 還是 left <= right 呢?
這可以從我們設置的左右邊界判斷出來,我們設置的 left = 0, right = n - 1,因此 [left, right] 是一個閉區間,那么當 left = right 時,[left, right] 區間同樣滿足我們的設置,因此,這個循環內應該是 left <= right。
target 和 arr[mid] 的判斷:當 target > arr[mid] 時,是應該 left = mid 還是 left = mid + 1 呢?
這和在 while 中的判斷是一個思路,當 target > arr[mid] 時,target 在 [mid + 1, r] 中,而非 [mid, r],因為顯然此時 mid 已經不可能等于 target 了,因此我們不需要再比較 target 和 arr[mid]。
同樣地,當 target < arr[mid] 時,也是類似的判斷。
循環不變量:left 和 right 的定義十分重要,因為在后面我們要不斷地維護這個定義,我們必須要保證是在 [left, right] 這個區間里尋找 target,這也就是 循環不變量,意思就是 left 和 right 的值雖然一直在變化,但是有一個聲明 在 [left, right] 區間內尋找 target 是永遠不變的,只要我們維護住這個 循環不變量,那么就可以保證我們的算法是正確的。當然,這里你也可以定義成 left = 0, right = n,即[left, right),那么此時定義就發生了變化,相應地,在 while 中為了維護這個定義,我們需要把條件改成 left < right,因為當 left = right 時,顯然 [left, right)是錯誤的,后面再查找時也要做相應的修改。
private int binarySearch(T arr[], int n, T target) { int left = 0, right = n - 1; // 在 [left, right] 區間內尋找 target while (left <= right) { // 當 left = right 時,區間 [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; }
不知道到這里大家有沒有發現一個 bug
因為 left 和 right 都是 int,所以當值足夠大時,在計算 mid = (left + right) / 2 時可能會發生整型溢出!
因此,為了避免這個問題,我們使用減法來計算。
完全正確的二分查找法
public int binarySearch(T[] arr, int n, T target) { int left = 0, right = n - 1; // 在 [left, right] 區間內尋找 target while (left <= right) { // 當 left = right 時,區間 [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; }測試
我們可以寫一個 Util 來幫助我們生成測試用例
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) { BinarySearchbs = new BinarySearch (); int n = (int)Math.pow(10, 7); // 用 10,000,000 數據測試 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/
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/69408.html
摘要:正文二分查找關于二分查找法二分查找法主要是解決在一堆數中找出指定的數這類問題。用二分查找法找尋上界與精確查找不同之處在于,精確查找分成三類大于,小于,等于目標數。 由一道題目引出的: 題目描述 給定一個有序的數組,查找某個數是否在數組中,請編程實現。 分析與解法 一看到數組本身已經有序,我想你可能反應出了要用二分查找,畢竟二分查找的適用條件就是有序的。那什么是二分查找呢? 二分查找可以...
摘要:為檢查長度為的列表,二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹,戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。 常見數據結構 簡單數據結構(必須理解和掌握) 有序數據結構:棧、隊列、鏈表。有序數據結構省空間(儲存空間小) 無序數據結構:集合、字典、散列表,無序...
摘要:為檢查長度為的列表,二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹,戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。 常見數據結構 簡單數據結構(必須理解和掌握) 有序數據結構:棧、隊列、鏈表。有序數據結構省空間(儲存空間小) 無序數據結構:集合、字典、散列表,無序...
摘要:為檢查長度為的列表,二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹,戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。 常見數據結構 簡單數據結構(必須理解和掌握) 有序數據結構:棧、隊列、鏈表。有序數據結構省空間(儲存空間小) 無序數據結構:集合、字典、散列表,無序...
摘要:測試用例輸入輸入輸入負數的輸入平方根為正整數的輸入平方根為小數的代碼實現寫二分查找代碼需要注意的三點循環退出條件。使用二分查找之前,判斷問題是否滿足二分查找的要求。 Time:2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿 題目:sqrt(x) Implement int sqrt(int x). Compute and retu...
閱讀 1869·2023-04-26 02:46
閱讀 1999·2021-11-25 09:43
閱讀 1143·2021-09-29 09:35
閱讀 2099·2019-08-30 15:56
閱讀 3423·2019-08-30 15:54
閱讀 2632·2019-08-29 16:35
閱讀 3120·2019-08-29 15:25
閱讀 3291·2019-08-29 14:01