題目說明

給定一個 升序排列且不重複的整數陣列 nums，以及一個目標值 target。

請找出：

如果 target 存在於陣列中，回傳它的索引位置；

如果不存在，則回傳它「應該插入」的位置，使得陣列仍維持升序。

要求時間複雜度為 O(log n)，所以要用 二分搜尋法 (Binary Search)。

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

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

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

解題思路

這題和「找數字」一樣，但要多思考一點：

如果沒找到，應該回傳「可以插入的 index」。

也就是說：

如果 target 比所有數都小 → 回傳 0

如果 target 比所有數都大 → 回傳 nums.length

否則找到「第一個大於等於 target」的位置。

步驟

設 left = 0, right = nums.length - 1

二分搜尋：

若 nums[mid] < target，代表應該在右邊，left = mid + 1

否則，應該在左邊或就是這個位置，right = mid - 1

迴圈結束後，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; // 向左找
}
}
// 沒找到就回傳 left，代表插入位置
return left;
}
}

複雜度分析

時間複雜度：O(log n)（二分搜尋）

空間複雜度：O(1)

心得

這題是「二分搜尋家族」的基礎題之一。
理解這題後，就能靈活應用在