lintcode：Search Insert Position 搜索插入位置

题目：

搜索插入位置

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

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

样例

[1,3,5,6]，5 → 2

[1,3,5,6]，2 → 1

[1,3,5,6]， 7 → 4

[1,3,5,6]，0 → 0

解题：

二分法直接搞，找到了返回下标，找不到结束时候的start ==end就是要插入的下标，非递归程序。

Java程序：

public class Solution {
    /** 
     * param nums : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
    public int searchInsert(int[] nums, int target) {
        // write your code here
        if(nums==null)
            return 0;
        if(nums.length==0)
            return 0;
        int start = 0;
        int end = nums.length;
        while(start<end){
            int median = (start+end)/2;
            if(nums[median]==target)
                return median;
            else if(nums[median]<target){
                start = median + 1;
            }else{
                end = median - 1;
            }
        }
        return start;
    
    }
}

总耗时: 1617 ms

修改一点，或者更好理解。

Python程序：

class Solution:
    """
    @param A : a list of integers
    @param target : an integer to be inserted
    @return : an integer
    """
    def searchInsert(self, nums, target):
        # write your code here
        if nums==None:
            return 0
        if len(nums)==0:
            return 0
        start = 0
        end = len(nums)-1 
        while start<=end:
            median = (start + end)/2
            if nums[median] == target:
                return median
            elif nums[median] < target:
                start = median + 1
            else:
                end = median - 1
        return start

总耗时: 474 ms