LeetCode---35. Search Insert Position

LeetCode—35. Search Insert Position

题目

https://leetcode.com/problems/search-insert-position/
给出一个有序数组和一个target，将这个target有序的插入到数组中，返回插入的index。

思路及解法

这道题还是比较简单的，时间复杂度n的解法很容易。之所以放到博客上来，是因为看了一个二分查找的方法，降了复杂度logn

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        // if(nums[0]>target) return 0;
        // for(int i=0; i<nums.length; i++){
        //     if(nums[i]==target)
        //         return i;
        //     if(i!=nums.length-1 && nums[i]<target && nums[i+1]>target)
        //         return i+1;
        // }
        // return nums.length;
        int low=0, high=nums.length-1;
        int mid=0;
        while(low<=high){
            mid = (low+high)/2;  //如果不是落在中间，就是落在偏low一边
            if(nums[mid]== target) return mid;
            else if(nums[mid]>target){
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        return low;
    }
}