浅谈不同二分算法的查找情况

二分算法原理比较简单，但是实际的算法模板却有很多，这一切都源于二分查找问题中的复杂情况和二分算法的边界处理，以下是博主对一些二分算法查找的情况分析。

1. 模板1

    int search(vector<int>& nums, int target) {int l = 0,r = nums.size() - 1;while(l <= r){int mid = (l + r) >> 1;if(nums[mid] == target) return mid;else if(nums[mid] > target) r = mid - 1;else l = mid + 1; }return -1; }

上述这种二分算法是较为常见的，可以用以查找某个数是否在一个序列中，如果在，就返回相应的下标；如果不在，就返回-1。

但是这种二分算法对于目标数有多个的情况，无法准确定位到位于左右边界的目标数，而且对于不存在目标数的序列，上述算法并不能找到第一个大于目标数或第一个小于目标数的下标。

2.模板2

为了解决第一类模板中无法解决的问题，第二类二分算法模板做出了改进。

对于序列中目标数存在多个的情况，这类模板实际提供两套模板，分别对应查找右边界和左边界。

    int find_left(vector<int>& nums,int target){int l = 0,r = nums.size() - 1;while(l < r){int mid = (l + r) >> 1;if(nums[mid] >= target)r = mid;elsel = mid + 1;}return l;}

    int find_right(vector<int>& nums,int target){int l = 0,r = nums.size() - 1;while(l < r){int mid = (l + r + 1) >> 1;if(nums[mid] <= target)l = mid;elser = mid - 1;}return l;}

上述两种二分算法分别能够定位到位于左右边界的目标数，且能够处理好边界问题，而不陷入死循环。

而对于目标数不在序列中的情况，上述两种算法也能很好处理。对于左边界的情况，它会找到当前序列中最接近目标数的位置(在将目标数按照顺序插入原序列的情况下)，且优先找大于目标数的位置，即优先找原序列第一个大于目标数的数；对于右边界的情况，它与左边界时的查找逻辑相同，唯一的区别在于它会优先找小于目标数的位置，即优先找原序列第一个小于目标数的数。

3. 总结

综合来看，第二类二分算法模板适用范围更广，能很好地应对各种二分查找的情况，且不会出现边界死循环问题，因此第二类二分算法中的两个模板更推荐使用。