法语网站建站公司_大学生网页设计作业成品_成都关键词快速排名_2345网址导航 中国最

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

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

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

二、解题思路

• 二分查找 是最优选择。我们可以利用二分查找在 O(log⁡n)O(\log n)O(logn) 时间内找到目标值或者它应插入的位置。
• 初始化两个指针 left 和 right，分别指向数组的开始和结束位置。
• 通过二分查找的方式，不断调整 left 和 right 的位置：
  • 如果中间元素 nums[mid] 等于目标值，直接返回 mid。
  • 如果 nums[mid] 小于目标值，说明目标值在右半部分，更新 left 指针。
  • 如果 nums[mid] 大于目标值，说明目标值在左半部分，更新 right 指针。
• 最终当 left 超过 right 时，left 的位置就是目标值应该插入的位置。

三、代码

四、复

class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;// 使用二分查找寻找 target 或插入位置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;  // 目标值小于中间值，搜索左半部分}}// 当退出循环时，left 就是目标值应该插入的位置return left;}
}

四、复杂度分析

• 时间复杂度：O(log⁡n)O(\log n)O(logn)，二分查找在每次迭代中将搜索范围减半。
• 空间复杂度：O(1)O(1)O(1)，只使用了常数级别的额外空间。