给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
题目要求“必须使用时间复杂度为 O(log n) 的算法”,因此,必然会想到二分查找算法。此题在标准二分查找的基础上增加了插入功能,如何实现呢?
假定插入位置为pos,则必然有nums[pos-1] < target < nums[pos],成立
假定元素在pos处存在,则必有nums[pos-1] < target == nums[pos]
合并为:nums[pos-1] < target <= nums[pos]
综上所述,我们得出最终目标:「在一个有序数组中找第一个大于等于 target的下标」
复杂度分析
时间复杂度:O(logn),n为nums的长度,二分查找算法时间复杂度为O(logn)。
空间复杂度:O(1),仅用常量空间存储变量。
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
let cnt = nums.count
var leftIdx = 0, rightIdx = cnt-1
//为啥是cnt,因为可以少处理边界情况,比如target比所有元素都大时,结果就是cnt
var ans = cnt
while leftIdx <= rightIdx {
let mid = (leftIdx + rightIdx) >> 1
if target <= nums[mid] {
rightIdx = mid - 1
ans = mid
}else {
leftIdx = mid + 1
}
}
return ans + 1
}
//由于要考虑到插入,位置为pos,有nums[pos-1] < target <= nums[pos],
//因此,问题转换为[找出第一个大于等于target的元素所在的位置]
- (NSInteger)searchInsert:(NSArray *)nums
target:(NSInteger)target {
NSInteger cnt = nums.count;
NSInteger left = 0, right = cnt - 1;
NSInteger ans = cnt;//赋值为cnt可减少边界情况处理,如target大于所有元素,那么就在最后一个位置插入
while (left <= right) {
NSInteger mid = (left + right) >> 1;
if (target <= [nums[mid] integerValue]) {
ans = mid;
right = mid - 1;
}else {
left = mid + 1;
}
}
return ans;
}