关于算法的边界问题

  有很多算法思路很简单，但是具体要实现的时候总会碰到一些麻烦的边界问题，这边整理一下。

二分查找

  思路不用多说，先贴一种可行的代码

int binarySearch(vector<int> nums,int tar){// 第一个边界int l = 0, r = nums.size()-1;// 第二个边界while(l<=r){int m = (l + r)/2;if(nums[m] == tar)return m;else if (nums[m]<tar)// 第三个边界l = m + 1;else // 第四个边界r = m - 1;}return -1;}

  从第一个边界我们就可以确定我们的搜索范围，这里r可以取nums.size()也可以取nums.size()-1，决定了我们的搜索范围区间是开还是闭，这里我选择了nums.size()-1，那么我们的搜索范围就应该是闭区间，那么在选择第二个范围时，即使l==r，依然是一个有意义的区间[l,r]，否则就是[l,r)，没有意义，所以我们这里的第二个边界应该取l<=r， 然后在第三第四个区间，自然就应该跳过明确不是target的位置m，分别取m-1或者m+1。这样边界条件就确定下来了，不需要死记硬背了。