重庆智能网站建设推荐,网站建设先做后,wordpress开发投稿,wordpress 多厂商插件题目描述#xff1a;
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target …题目描述
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
算法思想
由于该题指定算法时间复杂度 为O(log n)则该题的解题思路可以利用二分法来进行求解。 另外二分法一定要注意区间范围否则容易出现边界错误。
代码生成
class Solution {
public:int searchInsert(vectorint nums, int target) {int left 0,right nums.size()-1,middle;while(left right){middle (left right)/2;if(nums[middle] target)left middle 1;else if(nums[middle] target)right middle - 1;else return middle;}return left;}
};
