60.Search Insert Position

1.Description(Easy)

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 assumeNOduplicates in the array.

Example

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

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

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

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

Challenge

O(log(n)) time

2.Code

找到就返回，找不到就找最后一个比他小的数字，然后插在他后面。

注意最后比较target,start,end的大小关系，得出结论应该插在哪里。

public int searchInsert(int[] A, int target) {
        if(A==null || A.length==0){
            return 0;
        }

        int start=0,end=A.length-1;
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(A[mid]==target){
                return mid;
            }
            else if(A[mid]>target){
                end=mid;
            }
            else{
                start=mid;
            }           
        }

        if(A[start]>=target){
            return start;
        }
        else if(A[end]>=target){
            return end;
        }
        else{
            return end+1;
        }