本文共 837 字,大约阅读时间需要 2 分钟。
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2 示例 2:输入: [1,3,5,6], 2
输出: 1 示例 3:输入: [1,3,5,6], 7
输出: 4 示例 4:输入: [1,3,5,6], 0
输出: 0来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-insert-position 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。C++
方法1: 时间复杂度:O(n)class Solution { public: int searchInsert(vector & nums, int target) { for(int i=0;i=target) return i; return nums.size(); }};
方法2:折半查找
class Solution { /* 折半查找 时间复杂度: O(logn)*/public: int searchInsert(vector & nums, int target) { int left=0; int right=nums.size()-1; int mid; while(lefttarget){ right=mid-1; }else if(nums[mid]