二分查找是一種高效的查找算法，其核心在于每次比較都排除一半的查找范圍，從而快速定位目標值，但要求數據必須有序。實現方式有兩種：1. 循環實現通過 while(left
二分查找，也叫折半查找，是一種高效的查找算法。它的核心在于每次比較都排除掉一半的查找范圍，從而快速定位目標值。關鍵在于數據必須是有序的。
二分查找的Java實現，就是利用循環或者遞歸，不斷縮小搜索范圍，直到找到目標值或者確定目標值不存在。
解決方案
立即學習“Java免費學習筆記（深入）”；
二分查找的實現方式有兩種：循環和遞歸。這里分別給出示例代碼。
1. 循環實現
public class BinarySearch { public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止 (left + right) 溢出 if (arr[mid] == target) { return mid; // 找到目標值，返回索引 } else if (arr[mid] < target) { left = mid + 1; // 目標值在右半部分，更新左邊界 } else { right = mid - 1; // 目標值在左半部分，更新右邊界 } } return -1; // 沒有找到目標值，返回 -1 } public static void main(String[] args) { int[] arr = {2, 5, 7, 8, 11, 12}; int target = 13; int index = binarySearch(arr, target); if (index == -1) { System.out.println("Element is not found!"); } else { System.out.println("Element is found at index: " + index); } } }
這段代碼的核心是 while (left
2. 遞歸實現
public class BinarySearchRecursive { public static int binarySearchRecursive(int[] arr, int target, int left, int right) { if (left > right) { return -1; // 沒有找到目標值 } int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearchRecursive(arr, target, mid + 1, right); // 在右半部分遞歸查找 } else { return binarySearchRecursive(arr, target, left, mid - 1); // 在左半部分遞歸查找 } } public static void main(String[] args) { int[] arr = {2, 5, 7, 8, 11, 12}; int target = 13; int index = binarySearchRecursive(arr, target, 0, arr.length - 1); if (index == -1) { System.out.println("Element is not found!"); } else { System.out.println("Element is found at index: " + index); } } }
遞歸實現的核心在于 binarySearchRecursive 方法的自身調用。每次調用都傳入新的 left 和 right 值，縮小查找范圍。
二分查找的時間復雜度是 O(log n)，非常高效。但前提是數組必須是有序的。如果數組無序，需要先排序，排序的時間復雜度通常是 O(n log n)。
二分查找有哪些常見的變體？
二分查找的變體主要體現在對邊界條件的處理上。比如，查找第一個大于等于目標值的元素、查找最后一個小于等于目標值的元素等等。這些變體都需要對循環條件和邊界條件進行細致的調整。
以查找第一個大于等于目標值的元素為例，代碼如下：
public static int binarySearchFirstGreaterOrEqual(int[] arr, int target) { int left = 0; int right = arr.length - 1; int index = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] >= target) { index = mid; right = mid - 1; // 繼續在左半部分查找 } else { left = mid + 1; // 在右半部分查找 } } return index; }
關鍵在于 arr[mid] >= target 時，不僅要記錄 mid，還要繼續在左半部分查找，直到找到第一個大于等于目標值的元素。
二分查找在實際應用中有哪些場景？
二分查找廣泛應用于各種需要快速查找的場景，比如：
- 有序數組查找： 這是最直接的應用。
- 在排序數組中查找特定范圍的元素： 可以結合二分查找的變體實現。
- 數值逼近： 比如求一個數的平方根，可以通過二分查找不斷逼近。
- 在某些游戲或算法中進行決策： 比如猜數字游戲，或者在一些搜索算法中進行剪枝。
另外，數據庫索引的實現也經常用到二分查找的思想。
二分查找的邊界條件容易出錯，有什么好的調試技巧？
二分查找的邊界條件確實容易出錯。調試時，可以采用以下技巧：
- 仔細檢查循環條件： 確保循環條件 left
- 手動模擬： 選取一些典型的測試用例，手動模擬二分查找的過程，觀察 left、right 和 mid 的變化。
- 使用斷言： 在代碼中加入斷言，檢查 left、right 和 mid 的值是否符合預期。例如，可以斷言 left 始終小于等于 right。
- 編寫單元測試： 編寫充分的單元測試，覆蓋各種邊界情況，比如空數組、只有一個元素的數組、目標值在數組的開頭或結尾等等。
例如，可以添加如下斷言：
assert left <= right : "Left should be less than or equal to right";
通過這些調試技巧，可以有效地減少二分查找的錯誤。
