搜索插入位置

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

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

示例 1:

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

解题思路

• 1、使用二分查找算法来查找目标值在数组中的位置。
• 2、如果目标值存在于数组中，则返回其索引。
• 3、如果目标值不存在于数组中，则返回其应该插入的位置。

Java实现

public class SearchInsertPosition {

    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
//            int mid = left + (right - left) / 2;
            int mid = (left + right)  / 2;
            if (nums[mid] == target) {
                return mid; // 找到目标值，返回索引
            } else if (nums[mid] < target) {
                left = mid + 1; // 目标值在右半部分
            } else {
                right = mid - 1; // 目标值在左半部分
            }
        }

        return left; // 返回插入位置
    }

    public static void main(String[] args) {
        int[] mums = {1,3,5,6};
        int target = 5;
//        int target = 0;
//        int target = 7;
        int insert = new SearchInsertPosition().searchInsert(mums, target);
        System.out.println(insert);
    }
}

时间空间复杂度

• 时间复杂度：O(log n)，其中n为数组nums的长度。因为使用二分查找算法。

• 空间复杂度：O(1)。