LeetCode 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

思路一

for循环一个一个实验时间复杂度O（n）空间复杂度O（1）

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

思路二

因为数组是个排好序的可以用二分法

public static int searchInsert1(int[] nums,int target){
        int l=0;
        int r = nums.length-1;
        while (l <= r){
            int mid = (r + l);
            if (target > nums[mid]){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        return l;
    }

参考文章
https://leetcode.com/problems/search-insert-position/

Leetcode 35：搜索插入位置