下面是关于题目——搜索插入位置(二分算法)的题解,有需要借鉴即可。
1.题目
题目链接:LINK
2.二分求解
好好读题,我们发现要求我们的时间复杂度是logN,然后这个题目是一个有序数组且以target为断点具有“二段性”,所以需要用二分算法来求解。
那怎么进行划分呢?
因为题目中说,如果数组中有target就返回target的下标,如果没有,就返回最靠近target且大于target值的下标。
所以我们可以将数组划分为两部分,如下:
所以根据上面思路,我们结合之前做的题目(LINK),我们可以得出下面代码:
class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } if(target > nums[right]) return right + 1; return right; } };
3.总结
这个题目理解了二分边界算法很简单,属于一个基础题目。
EOF