【leetcode】35. Search Insert Position 给定数字插入有序数组的下标点
文章目录
1. 题目
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.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
2. 思路
二分查找第一个大于等于的位置。
3. 代码
耗时:9ms
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return bsearch(nums, 0, nums.size(), target);
}
int bsearch(vector<int>& nums, int i, int j, int target) {
if (i >= j) return i;
if (i+1 == j) { return nums[i] < target ? i+1 : i;}
int k = i + (j - i) / 2;
int vk = nums[k];
if (vk == target) {
return k;
} else if (vk > target) {
return bsearch(nums, i, k, target);
} else {
return bsearch(nums, k+1, j, target);
}
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论