二分查找（Binary Search）是一種常用的搜索算法，用于在有序數組中快速查找目標值。以下是二分查找的詳細理論知識、優缺點以及適用場景：
-
理論知識：
- 基本原理：二分查找通過比較目標值與數組的中間元素，將查找范圍縮小一半，直到找到目標值或查找范圍為空。
- 前提條件：二分查找要求數組必須是有序的，可以是升序或降序。
- 過程步驟：
- 初始化左右指針，分別指向數組的第一個和最后一個元素；
- 計算中間元素的索引；
- 比較目標值與中間元素的大小，根據比較結果調整左右指針；
- 重復上述過程直到找到目標值或查找范圍為空。
-
優點：
- 效率高：二分查找的時間復雜度為O(log n)，相較于線性查找的O(n)，性能更好。
- 算法簡單：二分查找的實現邏輯清晰，易于理解和實現。
- 適用于有序數組：只有在有序數組中才能應用二分查找，如果數組無序，則需要先進行排序。
-
缺點：
- 僅適用于有序數組：二分查找要求目標數組是有序的，如果數組無序，則無法應用二分查找。
- 需要額外空間：二分查找通常需要額外的指針來指示查找范圍，使得空間復雜度較高。
- 數據更新困難：如果目標數組需要頻繁更新，如插入、刪除等操作，需要重復進行排序，降低效率。
-
適用場景：
- 針對有序數組：二分查找適用于對有序數組進行快速查找，可以有效地減少查找時間。
- 大規模數據查找：對于大規模數據集合，二分查找能夠迅速縮小查找范圍，提高查找效率。
- 需要高效查找的場景：在對數據要求較高且需要快速查找的場景中，二分查找是一個好的選擇。
以上是關于二分查找的詳細理論知識、優缺點以及適用場景。希望對你有幫助！
接下來來到簡簡單單的小例題：
704. 二分查找
給定一個?n?個元素有序的（升序）整型數組?nums?和一個目標值?target??，寫一個函數搜索?nums?中的?target，如果目標值存在返回下標，否則返回?-1。
示例 1:
輸入:nums= [-1,0,3,5,9,12],target= 9 輸出: 4 解釋: 9 出現在nums中并且下標為 4
示例?2:
輸入:nums= [-1,0,3,5,9,12],target= 2 輸出: -1 解釋: 2 不存在nums中因此返回 -1
// 在有序數組中搜索目標值并返回其索引
public int search(int[] nums, int target) {int l = 0; // 左邊界int r = nums.length; // 右邊界，注意這里是數組長度，不是最后一個元素的索引while (l <= r) { // 當左邊界小于等于右邊界時執行循環int mid = (l + r) / 2; // 計算中間位置if (target == nums[mid]) { // 如果目標值等于中間值，返回中間索引return mid;}if (target < nums[mid]) { // 如果目標值小于中間值，縮小右邊界r = mid - 1;}if (target > nums[mid]) { // 如果目標值大于中間值，增大左邊界l = mid + 1;}}return -1; // 未找到目標值，返回-1
}?
)
