减治思想与二分查找的结合应用，有哪些要点总结？

本文共计5117个文字，预计阅读时间需要21分钟。

二分查找思想——二分查找细节总结+二分查找应用

二分查找适用于有序数组，时间复杂度为O(logn)。

思想：利用有序数组的性质，将查找区间一分为二，比较中间元素与目标值，逐步缩小查找范围。

应用：

1.在以O(logn)时间复杂度进行查找；

2.利用数组的有序性，直接排除一些元素，实现“减半查找。

减治思想——二分查找详细总结

二分查找应用于有序数组，可以在以\(O(\log(n))\)时间复杂度进行查找。其思想在于利用数组的有序性直接排除掉一些元素，这也是进行“减治”的地方。二分查找思想看起来简单，但是其边界条件其实很容易弄混，下面就对各种情况的二分查找（基础情形、左边界二分查找、右边界二分查找、应插入位置二分查找）进行详细的说明，完整的代码附在附录里面。

文章的的后半部分挑选了部分leetcode中典型应用二分思想的题目。

1. 二分查找的总结

这里贴上一份十分细节的讲解

二分查找写法的核心在于缩小查找的边界，也就是不断地缩小查找范围，使得目标值在范围内。当查找范围为空集或找到了目标值时，就可以结束循环。如果懂得这个道理，二分查找写起来就简单多了。

1.1 普通的二分查找

最普通的二分查找，我们只要求它能找到目标元素或返回异常值（返回-1表示未查找到目标元素）就好。其基本思想非常好理解，就是利用数组的有序性来筛掉不必要进行查找的元素。

注意：

二分查找最重要一点就是边界条件的判断，在整个数组中进行查询时，可以使用\(lo<=hi\)的写法，其中hi的起始值为nums.length - 1。