二分查找

class Solution {
    public int searchInsert(int[] nums, int target) {

        /**
         * 左闭右闭写法，left可以等于right
         */
        int left = 0;
        int right = nums.length - 1;

        while (left <= right){

            int mid = left + (right - left) / 2;

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

        /**
         * 在二分查找法的基础上，如果没有找到target，最后肯定left = right + 1
         * 即left指向的是大于target的第一个元素，也即是本题的答案
         */
        return left;
    }
}

/**
 * 时间复杂度 O(logn)
 * 空间复杂度 O(1)
 */

https://leetcode-cn.com/problems/search-insert-position/