LeetCode Search Insert Position：二分查找與雙指針雙解法

題目

有序無重複數組 nums，給定 target，返回索引（存在）或應插入位置（不存在）。

示例：[1,3,5,6], target=5→2, 2→1, 7→4, 0→0。

解法一：標準二分查找

public int searchInsert(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int m = (l + r) >>> 1;
        if (nums[m] == target) return m;
        else if (nums[m] < target) l = m + 1;
        else r = m - 1;
    }
    return l; // l 是第一個大於 target 的位置，即插入點
}

解法二：雙指針左右收斂

public int searchInsert(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        if (l == r) return nums[l] >= target ? l : l + 1;
        if (nums[l] == target) return l;
        if (nums[r] == target) return r;
        if (nums[l] < target) { if (l+1 <= r && nums[l+1] > target) return l+1; ++l; }
        if (nums[r] > target) { if (r-1 >= l && nums[r-1] < target) return r; --r; }
    }
    return l;
}

Python 版二分

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target: return m
            elif nums[m] < target: l = m + 1
            else: r = m - 1
        return l

核心洞察

二分查找結束時 l == r + 1，l 恰為第一個 ≥ target 的位置，即插入點。無需額外判斷邊界情況。