概述
二分查找作为经典的查找算法，思想比较简单，日常使用频繁。每次编写二分相关代码，经常会出现左右区间混乱，不知道如何划分区间等问题，造成做不出题目。
代码分析
- 区间的左右开闭问题:
[0, length - 1] - 循环边界:
while left < right，这样可以保证最终返回值left == right，随便返回哪个都可以 - 区间
[left.. right]可以划分为两种情况：
- 分为
[left..mid]和[mid+1..right]，分别对应right = mid和left = mid + 1 - 分为
[left..mid-1]和[mid..right]，分别对应right = mid-1和left = mid。在这种情况下，需要将mid = left + (right - left) / 2修改为mid = left + (right - left + 1) / 2，否则将出现死循环。
例如
nums = [1,2,3,5]，target = 5，若不修改mid计算，便会出现死循环
常见二分变体
查找第一个等于给定值的元素
第一个等于，逻辑上发生在数组左边，因此收缩右边界。
def firstEquals(nums, target): left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left)//2 # 防止溢出, //表示整除 if nums[mid] < target: left = mid + 1 else: right = mid # 收缩右边界 return left 复制代码
查找最后一个等于给定值的元素
最后一个等于，逻辑上发生在数组右边，因此收缩左边界。
def lastEquals(nums, target): left, right = 0, len(nums) - 1 mid = left + (right - left + 1) // 2 while left < right: if nums[mid] > target: right = mid - 1 else : left = mid return left 复制代码
查找第一个大于等于给定值的元素
第一个大于等于，逻辑上发生在数组左边，因此收缩右边界。
def firstLessEquals(nums, target): left, right = 0, len(nums) - 1 mid = left + (right - left) // 2 while left < right: if nums[mid] < target: left = mid + 1 else : right = mid return left 复制代码
查找最后一个小于等于给定值的元素
最后一个小于等于，逻辑上发生在数组右边，因此收缩左边界。
def firstLessEquals(nums, target): left, right = 0, len(nums) - 1 mid = left + (right - left + 1) // 2 while left < right: if nums[mid] > target: right = mid - 1 else : left = mid return left 复制代码
总结
通过多个角度的学习，自己暂且总结一个自用结论，当查找或者插入为第一个(偏左侧)时，收缩右边界right = mid；当为最后一个(偏右侧)时，收缩左边界left = mid
往期精彩文章
- 牛客最新前端JS笔试百题
- 抓取牛客最新前端面试题五百道 数据分析JS面试热点
- 原生JavaScript灵魂拷问(二)，你能全部答对吗？
- 原生JavaScript灵魂拷问(一)，你能答上多少？
- JavaScript之彻底理解原型与原型链
- JavaScript之预编译学习
- JavaScript之彻底理解EventLoop
- 《2w字大章 38道面试题》彻底理清JS中this指向问题
后语
如果大家感觉此文对你有一些帮助，希望能点个赞，鼓励鼓励阿包，阿包会不断努力的。另外如果本文章有问题，或者对文章其中一部分不理解，都可以评论区回复我，我们来一起讨论，共同学习，一起进步！
