https://leetcode.com/problems/search-insert-position
给定一个有序数组nums， 和一个target，问将这个target插入nums的位置；这里假设数组中没有重复值。
二分查找
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int lo = 0, hi = nums.size()-1;
while(lo < hi)
{
int mi = (lo+hi)>>1;
(nums[mi] < target ? lo = mi + 1 : hi = mi);
}
return (nums[lo] < target) ? lo +1 : lo;
}
};
退出while循环时，lo和hi相等，此时如果 target== nums[lo]，则返回lo，如果target > nums[lo]，则应该在 lo + 1 位置插入；如果 target < nums[lo]，则在lo位置插入；
网友评论