# 0035. Search Insert Position
###### tags: `Leetcode` `Easy` `Binary Search`

Binary Search的方法适合于已经有排过序的array，复杂度O(logN)

## 思路
唯一的小难点在于如果这个数不在array里面，return的值是start还是end，还是需要+-1。不过只需要用一个toy example就可以解决。

## Code

class Solution {
public:
    int binary_search(vector<int>& nums, int target){
        int start = 0;
        int end = nums.size()-1;
        while(start<end){
            int mid = start + (end-start)/2;
            if(nums[mid]>target){
                end = mid;
            }
            else if(nums[mid]<target){
                start = mid+1;
            }
            else{
                return mid;
            }
        }
        return start;
    }
    int searchInsert(vector<int>& nums, int target) {
        if(nums[0]>target){
            return 0;
        }
        else if(nums[nums.size()-1]<target){
            return nums.size();
        }
        int index = binary_search(nums,target);
        return index;
    }
};

## Result

Runtime: 4 ms, faster than **90.05%** of C++ online submissions for Search Insert Position.
Memory Usage: 9.7 MB, less than **71.80%** of C++ online submissions for Search Insert Position.

## Code in Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (nums[0] >= target) return 0;
        if (nums[len - 1] < target) return len;
        int left = 0, right = len;

        while (left < right){
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                left = mid + 1;
            }else right = mid;
        }
        return left;
    }
}

## 思路
二分查找的思路不难理解，但是边界条件容易出错，比如**循环结束条件中 left 和 right 的关系，更新 left 和 right 位置时要不要加 1 减 1**。

## Result
执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：37.8 MB, 在所有 Java 提交中击败了96.58%的用户