面试算法68：查找插入位置

题目

输入一个排序的整数数组nums和一个目标值t，如果数组nums中包含t，则返回t在数组中的下标；如果数组nums中不包含t，则返回将t按顺序插入数组nums中的下标。假设数组中没有相同的数字。例如，输入数组nums为[1，3，6，8]，如果目标值t为3，则输出1；如果t为5，则返回2。

分析

二分查找是在数组nums的某个范围内进行的，初始范围包括整个数组。每次二分查找都选取位于当前查找范围中间的下标为mid的值，然后比较nums[mid]和目标值t。如果nums[mid]大于或等于t，那么接着比较它的前一个数字nums[mid-1]和t。如果同时满足nums[mid]≥t并且nums[mid-1]＜t，那么mid就是符合条件的位置，返回mid即可。如果nums[mid]≥t并且nums[mid-1]≥t，那么符合条件的位置一定位于mid的前面，接下来在当前范围的前半部分查找。如果nums[mid]小于t，则意味着符合条件的位置一定位于mid的后面，接下来在当前范围的后半部分查找。
有两种情况需要特别注意。第1种情况是当mid等于0时如果nums[mid]依然大于目标值t，则意味着数组中的所有数字都比目标值大，应该返回0。第2种情况是当数组中不存在大于或等于目标值t的数字时，那么t应该添加到数组所有值的后面，即返回数组的长度。

解

public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 3, 6, 8};
        System.out.println(searchInsert(nums, 5));
    }

    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                if (mid == 0 || nums[mid - 1] < target) {
                    return mid;
                }

                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return nums.length;
    }
}