35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5 输出: 2

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-insert-position 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

二分查找(Binary Search) ,也叫折半查找，是一种高效的查找方法。 但是二分查找要求线性表必须采取顺序存储结构，而且表中元素按关键字顺序排列。最坏数据复杂度O(logN)

代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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