我的个人网站：https://hardyfish.top/

二分搜索（折半搜索）是一种在有序数组中查找某一特定元素的搜索算法。从定义可知，运用二分搜索的前提是数组必须是排好序的。另外，输入并不一定是数组，也有可能是给定一个区间的起始和终止的位置。

他的时间复杂度是 O(lgn)，非常高效。

他的缺点要求待查找的数组或者区间是排好序的。

对数组进行动态的删除和插入操作并完成查找，平均复杂度会变为 O(n)。

因此，当输入的数组或者区间是排好序的，同时又不会经常变动，而要求从里面找出一个满足条件的元素的时候，二分搜索就是最好的选择。

二分搜索一般化的解题思路如下。

从已经排好序的数组或区间中取出中间位置的元素，判断该元素是否满足要搜索的条件，如果满足，停止搜索，程序结束。

如果正中间的元素不满足条件，则从它两边的区域进行搜索。由于数组是排好序的，可以利用排除法，确定接下来应该从这两个区间中的哪一个去搜索。

通过判断，如果发现真正要找的元素在左半区间的话，就继续在左半区间里进行二分搜索。反之，就在右半区间里进行二分搜索。

例题：假设我们要从一个排好序的数组里 {1, 3, 4, 6, 7, 8, 10, 13, 14} 查看一下数字 7 是否在里面，如果在，返回它的下标，否则返回 -1。

递归写法的代码模板如下。

注意：

在计算 middle 下标的时候，不能简单地用 (low + hight) / 2，可能会导致溢出。

在取左半边以及右半边的区间时，左半边是 [low, middle - 1]，右半边是 [middle + 1, high]，这是两个闭区间。因为已经确定了 middle 那个点不是我们要找的，就没有必要再把它加入到左、右半边了。

对于一个长度为奇数的数组，例如：{1, 2, 3, 4, 5}，按照 low + (high - low) / 2 来计算，middle 就是正中间的那个位置，对于一个长度为偶数的数组，例如 {1, 2, 3, 4}，middle 就是正中间靠左边的一个位置。

时间复杂度是 O(logn)

非递归写法的代码模板如下。

为什么 while 循环的条件中是 return -1; } int middle = low + (high - low) / 2; //判断是否是下边界时，先看看 middle 的数是否为 target，并判断该数是否已为数组的第一个数，或者，它左边的一个数是不是已经比它小，如果都满足，即为下边界。 if (nums[middle] == target && (middle == 0 || nums[middle - 1] return searchLowerBound(nums, target, low, middle - 1); } else { return searchLowerBound(nums, target, middle + 1, high); } //不满足，如果这个数等于 target，那么就得往左边继续查找。 }

查找上边界的代码如下。

二分搜索可以用来查找一些模糊的边界。模糊的边界指，边界的值并不等于目标的值，而是大于或者小于目标的值。

例题：从数组 {-2, 0, 1, 4, 7, 9, 10} 中找到第一个大于 6 的数。

解题思路

在一个排好序的数组里，判断一个数是不是第一个大于 6 的数，只要它满足如下的条件：

该数要大于 6； 该数有可能是数组里的第一个数，或者它之前的一个数比 6 小。 只要满足了上面的条件就是第一个大于 6 的数。

代码实现

对于这道题，当不满足条件，而 middle 的数等于 target 的时候怎么办？举例说明，如果要求的是第一个大于 6 的数，而数组中有多个 6 挨在一起，而此时的 middle 指向其中的一个 6，程序必须得在右半边搜索。

二分搜索也能在经过旋转了的排序数组中进行。

例题：LeetCode 第 33 题，给定一个经过旋转了的排序数组，判断一下某个数是否在里面。

示例：给定数组为 {4, 5, 6, 7, 0, 1, 2}，target 等于 0，答案是 4，即 0 所在的位置下标是 4。

解题思路

对于这道题，输入数组不是完整排好序，还能运用二分搜索吗？

由于题目说数字了无重复，举个例子： 1 2 3 4 5 6 7 可以大致分为两类， 第一类 2 3 4 5 6 7 1 这种，也就是 nums[start] return -1; } //判断是否已超出了搜索范围，是则返回-1。 int middle = low + (high - low) / 2; //取中位数。 if (nums[middle] == target) { return middle; } //判断中位数是否为要找的数 if (nums[low] //是，则判断目标值是否在左半边。 return binarySearch(nums, target, low, middle - 1); //是，则在左半边继续进行二分搜索。 } return binarySearch(nums, target, middle + 1, high); //否，在右半边进行二分搜索。 } else { if (nums[middle] if (logs[high] == null) { return high; } return getUpperBound(logs, high * 2); } // 再运用二分搜索的方法去寻找日志的长度。 int binarySearch(String[] logs, int low, int high) { if (low > high) { return -1; } int middle = low + (high - low) / 2; if (logs[middle] == null && logs[middle - 1] != null) { return middle; } if (logs[middle] == null) { return binarySearch(logs, low, middle - 1); } else { return binarySearch(logs, middle + 1, high); } }` 最后

微信搜索：月伴飞鱼

1.日常分享一篇实用的技术文章，对面试，工作都有帮助

2.后台回复666，获得海量免费电子书籍，会持续更新