力扣 35 搜索插入位置

题意：给定一个有序数组和一个target数，找出target在数组中应该插入的位置

思路：二分查找，s开始index，m中间index，e结尾index

1. 如果中间的数是target返回中间的index
2. 如果中间的数小于target，更新s为m＋1
3. 如果中间的数大于target，更新e为m，因为如果数不存在，返回的index是较大的index，比如target是2，数组是0，3，返回的是1
4. 如果s＝＝e退出循环，返回s

思想：二分查找

复杂度：时间O（lgn)，空间O(1)

class Solution {
    public int searchInsert(int[] nums, int target) {
        int s = 0;
        int e = nums.length - 1;
        // 比所有的数都大，返回e+1
        if(target > nums[e])
            return e+1;
        // 二分查找
        while(s<e) {
            int m = s+(e-s)/2;
            if(nums[m] == target)
                return m;
            if(nums[m]<target) {
                s = m + 1;
            } else {
                e = m;
            }
        }
        return s;
    }
}