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

你可以假設數(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

思路：
搜索插入值，與查找指定數(shù)字類似，所以用二分法查找
另外，插入值下標是大于或等于查找值的，所以一定要默認index為size，并且在target小于等于nums[mid]時 給index賦值

class Solution {
    public int searchInsert(int[] nums, int target) {
        int size = nums.length;
        int l = 0;
        int r = size-1;
        int index = size;
        while(l<=r){
            int mid = (l+r) >> 1;
            if(target <= nums[mid]){
                r = mid -1;
                index=mid;
            } else{
                l = mid +1;
            }

        }
    return index;
    }
}

復雜度分析

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

偷學至 力扣（LeetCode）