二分查找有一个最关键的前提，查找的集合必须是排好序的！它的思想是分而治之。
给定数组：1，3，5，10，32，40，60，71，80，99
查找：60
1. 找到中间点
分两种情况：
1. 奇数个元素，很容易找到中间点
a, b, c, d, e -> c是中间点
2. 偶数个元素，我们取中间偏左位置
a, b, c, d, e, f -> c是中间点
所以对于我们的数组，32是我们的中间点。
2. 比较32和60，显然32 < 60，如果要查找的值比中间值大，那要查找的值一定在右半部分；反之，在左半部分。那么我们要在32的右半部分查找
1，3，5，10，32，40，60，71，80，99
3. 找到右半部分的中间点
40，60，71，80，99
4. 71 > 60，那接下来往左半部分查找
5. 找到左半部分的中间点
40，60
6. 40 < 60，往右半部分查找
7. 中间点是60
60
8. 查找结束，成功！
代码实现（javascript）
循环的方式：它不会造成函数调用栈膨胀。
function binarySearch(arr, val) { let start = 0; let end = arr.length - 1; while (start <= end) { let middleIndex = Math.floor((start + end) / 2); if (arr[middleIndex] === val) { return middleIndex; } else if (arr[middleIndex] < val) { start = middleIndex + 1; } else { end = middleIndex - 1; } } return -1; }
递归的方式：效率不及循环的方式，因为会有调用栈膨胀的问题。
function binarySearch(arr, val, start = 0, end = arr.length - 1) { const middleIndex = Math.floor((start + end) / 2); if (val === arr[middleIndex]) { return middleIndex; } if (start >= end) { return -1; } if (val < arr[middleIndex]) { binarySearch(arr, val, start, middleIndex - 1); } else { binarySearch(arr, val, middleIndex + 1, end); } }
二分查找的时间复杂度是O(log n)。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。