青岛网页设计制作,seo在哪可以学,新闻稿件,网站域名有了_网站如何建设每日一题之二分查找#xff08;一#xff09;
1.题目#xff08;搜索插入位置#xff09;
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间…每日一题之二分查找一
1.题目搜索插入位置
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
2.解题思路
因为数组是有序的排列数组且无重复元素所以可以使用二分来找下标
这里一共有四种情况
1数组中找到了目标元素返回当前目标元素的下标结束
2目标元素不存在应在数组的所有元素之前
3目标元素不存在应在所有的元素之后
4目标元素不存在应在数组中的某个位置
具体实现步骤
1.先找到这个数组的左边界再找到这个数组的右边界此时的范围就是整个数组
2.然后进行二分查找
1先找到中间位置的那个数然后与目标值进行比较
1 如果当前的数比目标值小的话那么左边界变为中间位置向右一个的位置继续进行查找
2 如果当前的数比目标值小的话那么右边界变为中间位置向左一个的位置继续进行查找
3 如果当前的数和目标值相等的话那么找到了
2当左边界比右边界大的时候结束查找
3.那要添加元素的位置就是右边界1的位置
3.代码
class Solution {
public:int searchInsert(vectorint nums, int target) {int left0;int rightnums.size()-1;while(leftright){//int mid(leftright)1;这里通过学习发现可以进行优化//优化如下int midleft(right-left)/2;//优化后的代码if(nums[mid]target){return mid;}if(nums[mid]target){rightmid-1;}if(nums[mid]target){leftmid1;}}return right1;}
};
