標(biāo)簽：數(shù)組陌兑，簡(jiǎn)易
問(wèn)題描述
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
給定已排序數(shù)組和目標(biāo)值。如果數(shù)組中存在目標(biāo)值泌绣，則返回其索引澎胡。否則孕荠，返回該值應(yīng)該插入位置的索引。
假設(shè)數(shù)組中不存在重復(fù)元素攻谁。
示例：
輸入: [1,3,5,6], 5
輸出: 2
輸入: [1,3,5,6], 2
輸出: 1
輸入: [1,3,5,6], 7
輸出: 4
輸入: [1,3,5,6], 0
輸出: 0
解決方案
方法一：遍歷法
遍歷數(shù)組稚伍，查找插入位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
if(len == 0) return 0;
int i = 0;
while(i < len && nums[i] < target)
i++;
return i;
}
};
算法分析
- 時(shí)間復(fù)雜度：Θ(n)。
- 程序運(yùn)行時(shí)間：8ms
方法二：二分查找法
基于二分查找的思想解決該問(wèn)題戚宦。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
if(len == 0) return 0;
if(target > nums[len - 1])
return len;
int low = 0;
int high = len - 1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if(nums[mid] == target)
return mid;
if(nums[mid] < target)
low = mid + 1;
else if (mid >= 1 && nums[mid - 1] < target)
return mid;
else high = mid - 1;
}
return 0;
}
};
算法分析
- 時(shí)間復(fù)雜度Θ(lgn)
- 運(yùn)行時(shí)間：8ms
