【手绘漫画】面试必考之二分查找（解题模板和深度剖析），中回
1、前言
昨天更的二分查找，就是传统的二分查找模板，是存在一些问题的，在返回左边界还是右边界这个问题上，比较容易出错！！！
【手绘漫画】面试必考之二分查找（解题模板和深度剖析），上回
那么有没有什么百搭的模板？
下面一起来看看吧！！！
本次的模板应对重复元素也可以~
下一期预计结合题目进行分析，争取一次性讲透了！！！
2、?代码
模板：
// Cint lower_bound(int* nums, int numsSize, int target){ int left = 0; int right = numsSize; while(left < right){ // 搜索区间[first, last)不为空 // 防溢出 int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } return left; // rightt也行，因为[left, right)为空的时候它们重合}# Pythondef lower_bound(array, first, last, value): while first < last: # 搜索区间[first, last)不为空 # 防溢出 mid = first + (last - first) // 2 if array[mid] < value: first = mid + 1 else: last = mid return first # last也行，因为[first, last)为空的时候它们重合在这里插入图片描述
3、?正文
1. 为什么 while(left < right) 而不是 while(left <= right) ?
首先注意 right = numsSize 而不是 numsSize - 1，即 [left, right) 左闭右开，所以 while 的终止条件是 left == right。
2. 为什么 left = mid + 1 和 right = mid ？
首先注意，我们是 [left, right) 左闭右开，所以下一步的区间，是 [left, mid) 或 [mid + 1, right)，不像之前是 -1 和 +1。
3. 为什么返回 left 而不是 right ？
一样的，while 终止的条件是 left == right，返回哪个都一样。
举报
腾讯云开发者
