35. Search Insert Position
题目:
解答:
使用二分查找,注意确定插入位置的方法。
下面代码注意注释的位置,为何可以这样优化掉。
代码:
class Solution {
public:
int searchInsert(vector<int>& nums, int begin, int end, int target){
if(begin >= end) return begin;
int middle = nums[(begin+end)/2];
if(middle == target){
return (begin + end) / 2;
}else if(middle > target){
return searchInsert(nums, begin, (begin + end) / 2, target);
}else{
return searchInsert(nums, (begin + end) / 2 + 1, end, target);
}
}
int searchInsert(vector<int>& nums, int target) {
//if(nums.empty()) return 0;
//if(nums[0] > target) return 0;
//if(nums[nums.size()-1] < target) return nums.size();
return searchInsert(nums, 0, nums.size(), target);
}
};
更新会同步在我的网站更新(https://zergzerg.cn/notes/webnotes/leetcode/index.html)