35 搜索插入位置

一、题目

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

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

二、题解

2.1 本题：搜索插入位置

找到 target 返回下标；找不到，返回 target 应该插入的位置。

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

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

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;  //二分查找这里是return -1;
    }
}

时间复杂度：$O(\log n)$

空间复杂度：$O(1)$

2.2 二分查找模板：

数组中有没有 target？如果有，返回下标；如果没有，返回 -1。

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

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

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

    return -1;
}

时间复杂度：$O(\log n)$

空间复杂度：$O(1)$

2.3 左边界模板：找第一个 >= target 的位置

适用问题：找第一个大于等于 target 的位置(本题也适用)

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

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

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

    return ans;
}

时间复杂度：$O(\log n)$

空间复杂度：$O(1)$

2.4 右边界模板：找最后一个 <= target 的位置

适用问题：找第一个大于等于 target 的位置

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

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

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

    return ans;
}

时间复杂度：$O(\log n)$

空间复杂度：$O(1)$