題目說明

35. Search Insert Position
    給你一個 已排序的整數陣列 nums 和一個目標值 target，請你找出目標值應該被 插入的位置，保持陣列排序。
    • 如果目標值已存在，回傳它的索引
    • 如果不存在，回傳它應插入的位置索引

範例

Input: [1,3,5,6], target = 5
Output: 2

Input: [1,3,5,6], target = 2
Output: 1

Input: [1,3,5,6], target = 7
Output: 4

Input: [1,3,5,6], target = 0
Output: 0

程式碼

Python 解法（二分搜尋）

def searchInsert(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left

Java 解法（二分搜尋）

class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
}

Java vs Python 差異
• Python 用 // 取整數除法，Java 直接 / 並避免溢位用 (right - left)/2
• Java 陣列長度 nums.length，Python 用 len(nums)
• 核心邏輯相同：二分搜尋決定目標位置或存在索引

複雜度分析
• 時間複雜度：O(log n)，每次迭代將搜尋範圍減半
• 空間複雜度：O(1)，只使用常數額外變數