剑指 Offer II 068. 查找插入位置

题目

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例1：

1 2	输入: nums = [1,3,5,6], target = 5 输出: 2

示例2：

1 2	输入: nums = [1,3,5,6], target = 2 输出: 1

示例3：

1 2	输入: nums = [1,3,5,6], target = 7 输出: 4

示例4：

1 2	输入: nums = [1,3,5,6], target = 0 输出: 0

示例5：

1 2	输入: nums = [1], target = 0 输出: 0

提示：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为无重复元素的升序排列数组
-10^4 <= target <= 10^4

解法一：

JAVA

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