二分查找边界问题小结二分查找边界问题小结

二分搜索使用二分搜索时，常常会被确定边界恶心到。
查阅了一定资料，文中说常用的两种边界的写法有：

下位中位数： lowerMedian = (length - 2) / 2
上位中位数:upperMedian = length /2

对于两种写法，由于大部分语言都是向下取整，因此通用写法：
注意！最好不要使用median = (length - 2) / 2来写如果length==1时会发生溢出！！！！
使用语言带的自动向下取整数是安全的！

median = (length - 1) / 2

指针的区间可以是开区间也可以是闭区间，也可以半开半闭。
使用上述的中位数转化位两头闭区间就会：

median = low + (high - low) / 2

注意：
这里不能使用加法，容易溢出：

median = ( low + high )/2 //overstack

此外有有个关键的地方是终结条件：
最好不要以 low == high 作为终结条件。会被跳过。

if (low ==high) { return (num[low] >= target)? low :++low; }

在找的元素不存在的情况下会被跳过而无法退出

正确的终结条件是：

low > high
此时搜索会结束

结束条件应该返回低位low!!!!
知乎的说法如下：（用本人的理解）

对于搜索过程中, high 位置的作用是减少搜索空间而 low 的作用是从0开始一直向着目标数字前进
搜索到的时候返回它，是一个一直逼近的过程。
对此对于高位的操作就可以放心惹
对于变种的题，只需找到目标位置与left位置关系即可。

代码如下：

int binarySearch(vector &nums, int target) { int start = 0; //利用向下取整的特性 int end = nums.size() - 1; //注意终止条件是start target) { start = mid - 1; } //搜索到的情况 else if (nums[mid] == target) { return mid; } } //未搜索到 //因为左边的start一直是逼近于接近值 //因此返回start是安全的 return start; }

推广：
上述使用于无重复元素的情况，对于有重复情况：
有以下的推广：

搜寻有序序列的某元素第一次出现的位置

也可以理解为虚招第一个大于等于目标元素的位置

作出以下修改
对应leetcode题目：
leetcode 35. search insert position

public: int searchInsert(vector &nums, int target) { int start = 0; int end = nums.size() - 1; while (start <= end) { int mid = (end - start) / 2 + start; if (nums[mid] >= target) { end = mid - 1; } else { start = mid + 1; } } return start; }

对比两者差别：

相等的情况：不能直接返回mid位置，而是一直做循环使得左边的游标left一直逼近target直到退出

不相等的情况，与一般的二分搜索相同，但是需要注意的是判断条件从start 因为在搜索要求是找到第一个元素的位置
对于target在目标数组中存在的情况最终会以end==start的情况退出
而没有搜索到的情况则是 start>end的情况结束的在这种情况下返回的是target该插入的位置，（因为采用的是
向下取整的mid，因此在插入过程中是完全ok的）

迭代器下的二分查找

#include #include using namespace std; int main(int argc, char const *argv[]) { vector v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; auto beg = v.begin(); auto end = v.end(); auto mid = v.begin() + (end - beg) / 2; int target = 2; while (mid != end && *mid != target) { if (target < *mid) { end = mid; } else { beg = mid + 1; } mid = beg + (end - beg) / 2; } if (end == mid) { printf("Not found.\n"); } else { printf("pos is %d", (int)(mid - v.begin())+1); } system("pause"); return 0; }

最后：二分搜索边界问题真恶心，最好多花时间搞懂，多写形成肌肉记忆！
参考自https://www.zhihu.com/question/36132386 知乎网

【二分查找边界问题小结】