如何写好一个二分查找
Published by powerfulyang on Nov 14, 2022
基础的二分写法
第一个,最基本的二分查找算法:
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid + 1 和 right = mid - 1
因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
const BinarySearch = (nums: number[], target: number) => { // [left, right] let left = 0; let right = nums.length - 1; while (left <= right) { const mid = left + Math.floor((right - right) / 2); if (target > nums[mid]) { left = mid + 1; } else if (target < nums[mid]) { right = mid - 1; } else { return mid; } } return -1; }
第二个,寻找左侧边界的二分查找:
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
const BinarySearch = (nums: number[], target: number) => { // [left, right) let left = 0; let right = nums.length; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (target > nums[mid]) { left = mid + 1; } else if (target < nums[mid]) { right = mid; } else { right = mid; } } if (nums[left] === target) { return left; } return -1; }
第三个,寻找右侧边界的二分查找:
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界
又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right,必须减一
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
const BinarySearch = (nums: number[], target: number) => { // [left, right) let left = 0; let right = nums.length; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (target > nums[mid]) { left = mid + 1; } else if (target < nums[mid]) { right = mid; } else { left = mid + 1; } } if (nums[left - 1] === target) { return left - 1; } return -1; };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
function threeSumClosest(nums: number[], target: number): number { const sorted = nums.sort((a, b) => a - b); let ans = nums[0] + nums[1] + nums[2]; for (let i = 0; i < nums.length - 2; i++) { let l = i + 1; let r = nums.length - 1; while (l < r) { const threeSum = nums[l] + nums[r] + nums[i]; if (Math.abs(threeSum - target) < Math.abs(ans - target)) { ans = threeSum; } if (threeSum > target) { r--; } else if (threeSum < target) { l++; } else { return target; } } } return ans; };