35. 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.

翻译

给定一个有序数组和一个目标值，如果找到该目标值，则返回目标值的下标，如果没找到，返回目标值应在位置的下标

假设数组中没有重复

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 1:

Input: [1,3,5,6], 0
Output: 0


我的答案

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

}
return nums.length;
}
}

大神答案

//采用二分法，减少计算复杂度

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