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.

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

读题

题目的意思就是给你一个有序的数组和一个数，找出这个数字在数组中的位置

思路

题目比较简单，可以遍历查找，也可以使用二分查找，遍历的话就是找到第一个大于等于target的数就返回，如果到了数组的末尾还没有找到，target就应该在数组的末尾

题解

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

或者使用二分的方式

 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;
    }