二分查找详解

🌈🌈😄😄

欢迎小伙伴来到茶色岛独家岛屿，本期会对二分查找进行详细的讲解，做好准备了么，那么开始吧。

🌲🌲🐴🐴

一、简介

二、查找思路：

三、二分法注意点

死循环：

二分法的左闭右闭区间：

四、总结

五、相关示例

一、简介

二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常简单，有点类似分治的思想。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二、查找思路：

如果中间值大于查找值，则往数组的左边继续查找，如果小于查找值这往右边继续查找。二分查找的思想虽然非常简单，但是查找速度非常长，二分查找的时间复杂度为O(logn)。

三、二分法注意点

1. while循环中 left 和 right 的关系，到底是 left <= right 还是 left < right
2. 迭代过程中 mid 和 right 或left的关系，到底是 right = mid - 1 还是 right = mid
3. 死循环问题
4. 二分法的左闭右闭区间

死循环：

产生缘由：

当循环条件 while (left <= right)时

因为 mid = left + ((right - left) / 2)，当 left = right 的时候，mid 的值不变

mid 不继续改变，由于right = mid，right 也不会改变，所以三个数字不会继续改变

循环条件 while (left <= right) 却仍然满足，不会跳出循环，产生死循环

二分法的左闭右闭区间：

这个是根据个人喜好决定的，我比较喜欢左闭右闭区间，不用考虑区间值是否丢失问题。

四、总结

二分法最重要的两个点，就是循环条件和后续的区间赋值问题

五、相关示例

34. 在排序数组中查找元素的第一个和最后一个位置_茶色岛^的博客-CSDN博客

LeetCode 744. 寻找比目标字母大的最小字母_茶色岛^的博客-CSDN博客

LeetCode 852. 山脉数组的峰顶索引_茶色岛^的博客-CSDN博客

LeetCode 441. 排列硬币_茶色岛^的博客-CSDN博客

LeetCode 367. 有效的完全平方数_茶色岛^的博客-CSDN博客

LeetCode 69. x 的平方根_茶色岛^的博客-CSDN博客

LeetCode 374. 猜数字大小_茶色岛^的博客-CSDN博客

LeetCode 35. 搜索插入位置_茶色岛^的博客-CSDN博客

LeetCode 278. 第一个错误的版本_茶色岛^的博客-CSDN博客

LeetCode 704. 二分查找_茶色岛^的博客-CSDN博客

LeetCode 33. 搜索旋转排序数组_茶色岛^的博客-CSDN博客

LeetCode 81. 搜索旋转排序数组 II_茶色岛^的博客-CSDN博客 

LeetCode 74. 搜索二维矩阵_茶色岛^的博客-CSDN博客 

以上是我最近写的一些博客，希望会对小伙伴提供帮助，不懂的可以私信哦，我们一起探讨。