一.原题如下
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
二.示例如下
三.分析
首先最重要的一点就是数组是一个排序数组，并且是按升序排序。假设目标值target存在于数组中，如下：
依次遍历数组，当i=2时满足目标值，返回索引值2即可。当目标值不存在于数组中时，如下：
同样遍历数组，因为数组是按照升序进行排序的，所以当数组遍历到的数组元素大于目标值target时，即3>2，说明该目标值不存在于数组中，此时返回待插入的位置，依旧是数组索引i的值。
所以根据分析不管找到目标值还是没有找到目标值，都返回数组索引i的值。
四.代码实现
//C实现
int searchInsert(int* nums, int numsSize, int target){
for(int i=0;i
if(nums[i]>=target)
{
return i;
}
}
return numsSize;//遍历到数组最后
}
//C++实现
class Solution {
public:
int searchInsert(vector& nums, int target) {
for(int i=0;i
if(nums[i]>=target)
{
return i;
}
}
return nums.size();
}
};
我是老胡，感谢阅读！❤️ ❤️
