Problem: 35. 搜索插入位置
給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為 O(log n) 的算法。

整體思路

這段代碼旨在解決一個經典的搜索問題：搜索插入位置 (Search Insert Position)。問題要求在一個已排序的數組 nums 中查找目標值 target。如果找到，則返回其索引；如果未找到，則返回它應該被插入的位置的索引，以保持數組的有序性。

該算法采用的核心方法是二分查找（Binary Search），這是一種在有序數據集中進行高效查找的算法。此特定實現方式是一種常見的“左閉右開”區間模板，其目標是找到第一個大于或等于 target 的元素的位置。

算法的整體思路可以分解為以下步驟：

1. 定義搜索區間：

   • 算法使用兩個指針 left 和 right 來定義一個左閉右開的搜索區間 [left, right)。
   • left 初始化為 0，right 初始化為數組的長度 nums.length。這意味著初始搜索范圍覆蓋了整個數組的所有合法索引以及末尾的插入位置。

2. 循環搜索：

   • 算法的主體是一個 while (left < right) 循環。這個條件意味著只要搜索區間 [left, right) 還不是空的（即至少包含一個元素），搜索就繼續。當 left == right 時，區間為空，循環終止。
   • 在循環內部，計算中間位置 mid。
   • 比較與分區：將中間位置的元素 nums[mid] 與 target進行比較，以縮小搜索范圍：
     • Case 1: nums[mid] < target: 如果中間值小于目標值，說明 target 必定在 mid 的右側。因此，我們可以安全地排除掉 mid 及其左側的所有元素。通過 left = mid + 1，將搜索區間更新為 [mid + 1, right)。
     • Case 2: nums[mid] >= target: 如果中間值大于或等于目標值，說明 target 可能就是 nums[mid]，或者在 mid 的左側。在這種情況下，mid 本身就是一個潛在的答案（可能是第一個大于等于target的位置）。我們不能排除 mid，因此通過 right = mid，將搜索區間更新為 [left, mid)。

3. 確定最終結果：

   • 循環最終會因為 left 和 right 相遇而終止。此時，left (或 right) 指向的位置就是“插入點”。
   • 這個位置的含義是：它是數組中第一個大于或等于 target 的元素的索引。
   • 如果 target 存在于數組中，這個位置就是 target 首次出現的索引。
   • 如果 target 不存在，這個位置就是 target 應該被插入以保持數組有序的索引。
   • 因此，直接返回 left 即可。

完整代碼

class Solution {/*** 在一個已排序的數組中查找目標值，如果找到則返回其索引，* 否則返回它應該被插入的位置的索引。* @param nums 一個已升序排序的整數數組* @param target 目標整數* @return 目標值的索引或插入位置的索引*/public int searchInsert(int[] nums, int target) {// left: 搜索區間的左邊界，初始為 0。int left = 0;// right: 搜索區間的右邊界，初始為數組長度。// 定義了一個左閉右開的搜索區間 [left, right)。int right = nums.length;// 當左邊界小于右邊界時，搜索空間不為空，循環繼續。// 循環終止條件是 left == right。while (left < right) {// 計算中間索引。>> 1 是除以2的位運算，效率高且能防止(left+right)整數溢出。int mid = (left + right) >> 1;// 如果中間值小于目標值if (nums[mid] < target) {// 說明目標值必定在右半部分 [mid + 1, right) 中。// 更新左邊界，排除 mid 及左邊的所有元素。left = mid + 1;} else {// 如果中間值大于或等于目標值// 說明目標值在左半部分 [left, mid] 中，或者 mid 本身就是目標。// 更新右邊界，將 mid 包含在新的搜索區間 [left, mid) 內作為可能的答案。right = mid;}}// 循環結束時，left 和 right 相遇。// 該位置就是插入點，它指向數組中第一個大于或等于 target 的元素。// 這既是 target 的插入位置，也是當 target 存在時其首次出現的索引。return left;}
}

時空復雜度

時間復雜度：O(log N)

1. 算法核心：該算法是二分查找。
2. 計算依據：
   • 在 while 循環的每一次迭代中，搜索區間 [left, right) 的大小（即 right - left）都會被大約減半。
   • 假設初始的搜索區間大小為 N。經過 k 次迭代后，區間大小變為 N / 2^k。
   • 循環在區間大小縮減到 1 或 0 時終止，即 N / 2^k ≈ 1。
   • 解這個方程得到 2^k ≈ N，所以 k ≈ log?(N)。
   • 由于循環的迭代次數與 N 的對數成正比，因此時間復雜度為 O(log N)。

空間復雜度：O(1)

1. 主要存儲開銷：算法在執行過程中，只使用了少數幾個整型變量來存儲狀態，如 left, right, mid。
2. 計算依據：
   • 這些變量的數量是固定的，不隨輸入數組 nums 的大小 N 的變化而改變。
   • 算法沒有創建任何新的、與輸入規模成比例的數據結構（如新數組或哈希表）。

綜合分析：
算法所需的額外輔助空間是常數級別的。因此，其空間復雜度為 O(1)。