• 題目需求

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。
你可以假設(shè)數(shù)組中無重復(fù)元素。

示例 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ù)組，從下標(biāo)為0開始向后遍歷，當(dāng)值大于等于目標(biāo)值，返回下標(biāo)值，時(shí)間復(fù)雜度O(n)

   public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target)
                return i;
        }
        return nums.length;
    }

2：二分搜索,時(shí)間復(fù)雜度O(log N)

  public int binarySearchInsert(int[] nums, int target) {
        if (nums.length == 0) return 0;
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (target == nums[m] || ((m == 0 || target > nums[m - 1]) && target < nums[m])) return m;
            if (target > nums[m]) l = m + 1;
            else r = m - 1;
        }
        return nums.length;
    }