在阿里巴巴做网站多少钱,装修设计 在线,建设网站的技术方案,销售网站建设价格插入的位置 题目及要求二分查找在main内使用 题目及要求
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1: … 插入的位置 题目及要求二分查找在main内使用 题目及要求
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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] 104 nums 为 无重复元素 的 升序 排列数组 -104 target 104
二分查找
思路使用二分查找首先初始化左右指针然后在每一次循环中计算中间位置 mid并与目标值进行比较。如果中间位置的元素等于目标值则返回该位置如果中间位置的元素大于目标值则将右指针移动到 mid - 1 的位置如果中间位置的元素小于目标值则将左指针移动到 mid 1 的位置。通过不断变化搜索范围最终找到目标值的索引位置或应该插入的位置
class Solution {
public:int searchInsert(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright){int mid(leftright)/2;if(nums[mid]target){return mid; //返回目标值的索引}else if(nums[mid]target){rightmid-1;}else{leftmid1;}}return left; //返回插入的位置}
};在main内使用
int main() {vectorint nums {1, 3, 5, 6};int target 4;Solution solution;int index solution.searchInsert(nums, target);if (nums[index] target) {cout 目标值 target 的索引为 index endl;} else {cout 目标值 target 应该插入到索引为 index 的位置上 endl;}return 0;
}
