搜索插入位置

题解思路

本题要求在一个 有序数组 中找到目标值的索引，或者确定它应该插入的位置。由于数组已经是 升序排列，我们可以使用 二分查找算法（Binary Search），该算法的时间复杂度为 O(log n)，满足题目要求。

二分查找方法：

1. 设定左右指针 left 和 right，初始值分别为 0 和 n-1。
2. 进行 循环查找，直到 left 超过 right：
   • 计算中间索引 mid = (left + right) // 2。
   • 如果 nums[mid] == target，返回 mid 作为目标值的索引。
   • 如果 nums[mid] < target，说明目标值在 mid 右侧，调整 left = mid + 1。
   • 如果 nums[mid] > target，说明目标值在 mid 左侧，调整 right = mid - 1。
3. 若未找到目标值，返回 left 作为应插入的位置。

复杂度分析

• 时间复杂度：O(log n)，因为每次搜索都将搜索范围缩小一半。
• 空间复杂度：O(1)，仅使用了常数级的额外空间。

Python 代码

class Solution:
    def searchInsert(self, nums, target):
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid  # 找到目标值，返回索引
            elif nums[mid] < target:
                left = mid + 1  # 目标值在右侧
            else:
                right = mid - 1  # 目标值在左侧
        
        return left  # 未找到目标值，返回插入位置

# 读取输入
n, target = map(int, input().split())
nums = list(map(int, input().split()))

# 计算结果并输出
solution = Solution()
print(solution.searchInsert(nums, target))

Java 代码

import java.util.Scanner;

public class Main {
    public 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; // 未找到目标值，返回插入位置
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int target = scanner.nextInt();
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.searchInsert(nums, target));
    }
}

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 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; // 未找到目标值，返回插入位置
    }
};

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    Solution solution;
    cout << solution.searchInsert(nums, target) << endl;
    
    return 0;
}

题目内容

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

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

输入描述

• 第一行：两个整数，第一个整数表示数组的长度 $n$，第二个整数表示目标值 $target$。
• 第二行：包含 $n$ 个整数的数组 $nums$，数组中的元素按升序排列，且无重复元素。

输出描述

一个整数，表示目标值 $target$ 在数组 $nums$ 中的索引。如果 $target$ 不存在于数组中，则输出它应该被插入的位置。

样例1

输入

4 5
1 3 5 6

输出

2

样例2

输入

4 2
1 3 5 6

输出

1

样例3

输入

4 7
1 3 5 6

输出

4

提示

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