leetcode: Search Insert Position

问题描述：

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

原问题链接：https://leetcode.com/problems/search-insert-position/

 

问题分析

　　应该说这是二分查找方法的另一个变体。针对这个排序的数组，我们要找到一个可以插入目标元素的位置。这里可以根据几种情况来考虑。首先，数组里面没有元素。那么肯定返回的是０。另外的几种情况就是如果目标值比数组的第一个元素小，那么肯定也是返回０。而如果这个目标元素比数组的最后一个元素大，那么应该返回数组的长度值，也就是nums.length。

　　剩下要找目标元素的位置就应对的是常规的情况了。这个目标元素肯定在数组的中间某个位置。于是就可以用常规的二分查找。如果找到了就返回。而如果没找到呢？我们返回l的值就可以了。为什么呢？因为在循环while(l <= r)的这个循环跳出的情况下，当没有找到匹配的值时，l最终取的值是要比r大的。而在循环里所有l的取值都比目标值要小。它们最终退出时会有l == r的情况之后l = l + 1的值了。这个值比l原来的那个值要大，但是从r的取值情况来看它是正好比目标值要大的。而我们要找的就是正好在一个比目标值小和一个比目标值大的数中间。所以正好取l就可以了。

　　详细代码实现如下：

 

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

    这方法是二分查找的简单变化，所以其时间复杂度还是一样的O(logN)。