LeetCode35：搜索插入位置

原题地址：. - 力扣（LeetCode）

题目描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

解题思路

1. 首先检查数组是否为空或不存在，如果是，则返回 -1。
2. 初始化两个指针 start 和 end，分别指向数组的开始和结束位置。
3. 使用 while 循环进行二分查找，直到 start 和 end 相遇或相邻。
4. 在每次迭代中，计算中间索引 midd，并比较 nums[midd] 与 target。
5. 如果 nums[midd] 等于 target，则返回 midd。
6. 如果 nums[midd] 大于 target，则将 end 移动到 midd，因为 target 应该在 midd 的左侧。
7. 如果 nums[midd] 小于 target，则将 start 移动到 midd，因为 target 应该在 midd 的右侧。
8. 循环结束后，检查 start 和 end 位置的元素是否等于 target，如果是，则返回相应的索引。
9. 如果 target 不在数组中，则根据 target 与数组中最后一个元素的大小关系，返回 start+1 或 end+1。

源码实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 如果数组为空或不存在，返回-1
        if (null == nums || nums.length == 0) {
            return -1;
        }
        // 初始化搜索的起始和结束索引
        int start = 0;
        int end = nums.length - 1;
        // 用于计算中间索引
        int midd;
        
        // 使用二分查找直到start和end相遇或相邻
        while (start + 1 < end) {
            // 计算中间索引
            midd = start + (end - start) / 2;
            // 如果中间元素等于目标值，返回中间索引
            if (nums[midd] == target) {
                return midd;
            } else if (nums[midd] > target) {
                // 如果中间元素大于目标值，更新结束索引
                end = midd;
            } else {
                // 如果中间元素小于目标值，更新开始索引
                start = midd;
            }
        }
        
        // 检查start位置的元素是否等于目标值
        if (nums[start] == target) {
            return start;
        }
        
        // 检查end位置的元素是否等于目标值
        if (nums[end] == target) {
            return end;
        }
        
        // 如果目标值大于end位置的元素，返回end+1
        if (target > nums[end]) {
            return end + 1;
        } else {
            // 否则，返回start+1
            return start + 1;
        }
    }
}

复杂度分析

• 时间复杂度：O(log n)，其中 n 是数组 nums 的长度。这是因为每次迭代都会将搜索范围减半，所以总的迭代次数是对数级别的。

• 空间复杂度：O(1)，因为除了输入数组外，我们只使用了常数个额外的变量（start、end 和 midd），所以空间复杂度是常数级别的