#P4023. 搜索插入位置
-
ID: 2239
Tried: 77
Accepted: 30
Difficulty: 2
搜索插入位置
题目内容
给定一个排序数组和一个目标值，在数组中找到目标值，并输出其索引。如果目标值不存在于数组中，输出它将会被按顺序插入的位置。
请必须使用时间复杂度为 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<=104
- −104<=nums[i]<=104
- nums为 无重复元素 的 升序 排列数组
- −104<=target<=104
搜索插入位置
题解思路
本题要求在一个 有序数组 中找到目标值的索引，或者确定它应该插入的位置。由于数组已经是 升序排列，我们可以使用 二分查找算法（Binary Search），该算法的时间复杂度为 O(log n)，满足题目要求。
二分查找方法：
- 设定左右指针
left和right，初始值分别为0和n-1。 - 进行 循环查找，直到
left超过right：- 计算中间索引
mid = (left + right) // 2。 - 如果
nums[mid] == target，返回mid作为目标值的索引。 - 如果
nums[mid] < target，说明目标值在mid右侧，调整left = mid + 1。 - 如果
nums[mid] > target，说明目标值在mid左侧，调整right = mid - 1。
- 计算中间索引
- 若未找到目标值，返回
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;
}