搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 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
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0,right = nums.size() - 1;
int mid;
while(left < right)
{
mid = (left + right) / 2;
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
//没有找到的情况 left == right
return target <= nums[left] ? left : right+1;
}
};
直接使用二分查找法降低时间复杂度为O(log n) ,然后再二分查找的基础上修改一下,当left == right的情况来处理数组中没有目标数据的情况,但是仅仅是做了一个下标处理,并没有将数据真正插入到数组之中,因为题目仅仅是要返回目标数据应该被插入的位置
下标处理考虑三种情况
1.数据插入到数组头部
如果数据最小,那么循环结束的left == right == 0,因此直接返回left
2.数据插入到数组尾部
如果数据最大,那么循环结束的left == right == nums.size() - 1,因此返回left+1或者right+1即可
3.数据插入到数组中部
target > 最终的nums[left]则返回left+1或者right+1
target < 最终的nums[left]则返回left或者right即可
target = nums[left]的情况: 数组中只有一个元素[1] target = 1,直接返回left即可
