原题地址：. - 力扣（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] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
解题思路
- 首先检查数组是否为空或不存在，如果是，则返回
-1。- 初始化两个指针
start和end，分别指向数组的开始和结束位置。- 使用
while循环进行二分查找，直到start和end相遇或相邻。- 在每次迭代中，计算中间索引
midd，并比较nums[midd]与target。- 如果
nums[midd]等于target，则返回midd。- 如果
nums[midd]大于target，则将end移动到midd，因为target应该在midd的左侧。- 如果
nums[midd]小于target，则将start移动到midd，因为target应该在midd的右侧。- 循环结束后，检查
start和end位置的元素是否等于target，如果是，则返回相应的索引。- 如果
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），所以空间复杂度是常数级别的
