AlgoPressAppearance
0035-搜索插入位置
https://leetcode.cn/problems/search-insert-position
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 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 示例 4:
输入: nums = [1,3,5,6], target = 0 输出: 0 示例 5:
输入: nums = [1], target = 0 输出: 0
提示:
1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums 为无重复元素的升序排列数组 -10^4 <= target <= 10^4
思路
先按照常规二分法查找目标位置，如果找到直接返回。 当没有找到的时候，需要返回插入的位置，这个时候我们需要判断，循环结束的时候 left 的位置 left 可能是从左边没有找到 他自己+1, 也可能是右边 right 没找, right-1了 所有我们最后需要判断 nums[left] 的数值是否大于 target 如果大于，那么就返回left+1， 如果 nums[left] < target 那说明就需要插入到 left 所在位置。 最后注意判断 left 是否一直走到最右，如果是，那就在最后插入，位置为 nums.Length
参考代码
其实最后一段left的判断没有必要，直接返回 left 值就好，因为
csharp
public class Solution {
public int SearchInsert(int[] nums, int target) {
int left = 0;
int right = nums.Length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1;
}
else if(nums[mid] > target){
right = mid - 1;
}
else{
return mid;
}
}
//没找到
// if(left < nums.Length){
// return nums[left] > target ? left : left + 1;
// }
// else{
// return nums.Length;
// }
return left;
}
}
参考代码优化
判断 mid 是否是小于 target, 如果是 left 往右移动。 考虑到循环结束，如果 left 一直没有移动过，那么0就是要返回的值 如果 left 移动过，但是他的判断条件一直是 < target 的，所以结束的时候 , 同样 left 就是要插入的位置 如果 left 一直遍历到最后 , num[mid] 是大于 target 的，那么 left+1 就是 nums.Length 此时返回 left 同样是问题的答案
csharp
public class Solution{
public int SearchInsert(int[] nums, int target){
int left = 0;
int right = nums.Length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid+1;
}
else{
right = mid-1;
}
}
return left;
}
}
另一种写法
csharp
public class Solution {
public int SearchInsert(int[] nums, int target) {
int left = 0;
int right = nums.Length;
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}
else if(target > nums[mid]){
left = mid + 1;
}
else{
right = mid;
}
}
return left;
}
}