二分查找
簡介
二分查找（Binary Search）是一種高效的搜索演算法，用于在 有序陣列（或有序串列） 中查找特定元素的位置，它將目標值與陣列的中間元素進行比較，并根據比較結果縮小搜索范圍，直到找到目標值或確定目標值不存在，
二分查找的關鍵點是每次迭代都能將搜索范圍縮小一半，因此其時間復雜度為 O(log n) ，其中 n 是陣列的長度，這使得二分查找成為處理大規模有序資料集的有效演算法，
代碼演示
二分查找的基本思想：
- 首先，確定陣列的左邊界
left和右邊界right，通常初始時left = 0，right = 陣列長度 - 1， - 在每一次迭代中，計算中間元素的索引
mid，使用floor函式將中間值可能的小數部分向下向下取整， - 將目標值與中間元素
nums[mid]進行比較：- 如果
nums[mid]等于目標值，表示找到了目標值，回傳mid， - 如果
nums[mid]大于目標值，表示目標值可能在左側，更新查詢邊界right = mid - 1， - 如果
nums[mid]小于目標值，表示目標值可能在右側，更新查詢邊界left = mid + 1，
- 如果
- 重復執行步驟 2 和步驟 3，直到找到目標值或搜索范圍為空（
left > right），此時目標值不存在，回傳 -1，
以下是 JavaScript 代碼演示：
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
進階練習
LeetCode - 搜索插入位置
本文來自博客園，作者：Lianginx，轉載請注明原文鏈接：https://www.cnblogs.com/lianginx/p/binary-search.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/556946.html
標籤：其他
上一篇：Stable Diffusion AIGC：3步成為P圖大師
下一篇：返回列表