一、問題

給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值，并返回其索引。如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置?？梢约僭O數(shù)組中無重復元素。

示例 1：輸入：[1,3,5,6]，5輸出：2

示例 2：輸入：[1,3,5,6]，2輸出：1

示例 3：輸入：[1,3,5,6]，7輸出：4

示例 4：輸入：[1,3,5,6]，0輸出：0

二、解答

1??方法一：二分查找

假設題意是在排序數(shù)組中尋找是否存在一個目標值，那么立馬就能想到利用二分法在 O(logn) 的時間內(nèi)找到是否存在目標值。但這題還多了個額外的條件，即如果不存在數(shù)組中的時候需要返回按順序插入的位置，那還能用二分法么？答案是可以的，只需要稍作修改即可?？紤]這個插入的位置 pos，它成立的條件為：nums[pos-1] < target ≤ nums[pos]

其中 nums 代表排序數(shù)組。由于如果存在這個目標值，我們返回的索引也是 pos，因此可以將兩個條件合并得出最后的目標：「在一個有序數(shù)組中找第一個大于等于 target 的下標」。

問題轉化到這里，直接套用二分法即可，即不斷用二分法逼近查找第一個大于等于 target 的下標 。ans 初值設置為數(shù)組長度可以省略邊界條件的判斷，因為存在一種情況是 target 大于數(shù)組中的所有數(shù)，此時需要插入到數(shù)組長度的位置。

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

①時間復雜度：O(logn)，其中 n 為數(shù)組的長度。二分查找所需的時間復雜度為 O(logn)。
②空間復雜度：O(1)。只需要常數(shù)空間存放若干變量。