还记的小时候玩过这样一个游戏吗？有一个商品价格未知，给定了这个件商品的价格区间，来猜商品的价格，如果没猜中价格的话会反馈是猜大了还是猜小了然后继续猜知道猜对为止。小时候玩这个游戏的时候玩多了自然而然地发现，如果每次猜区间的中间的话，我会更有效率地得到答案。这就是二分查找的基本思想！
概念&关键（二分查找的思想）
二分查找是减而治之思想的一种体现，这里的二分只是一种分区间、缩小区间的概念，并不一定就是对半分，每次分三等分、四等分、N等分都是没有问题的！这里的查找毋庸置疑代表的意思就是查询目标值，所以我们这个算法多用在查找某个目标值的思路上。
二分查找最重要的思路就是确定区间，然后通过一定的判断去缩小、移动区间，直到锁定答案或者目标区间为止。所以要想用到二分查找，确定区间是很重要的一步，而要想很好地确定区间或改变区间，我们的区间往往是需要有序的，这样我们才能很好地确定目标值与区间间的关系。所以在遇到有序、查找、数组等字眼的时候，你可以好好想想是不是该用二分查找来解决问题。遇到查找这一关键字的时候，要记得问问自己区间是否可以有序化？如果能有序化那是不是就可以用二分查找？
Why it？
学习知识的目的在于更好地运用知识去改变，所以我们要想学会一个算法我们得知道为什么要用它，在哪里运用它。
首先我们知道二分查找一般是用于从一个集合中找寻一个目标值。那找目标值我们直接用遍历解决不就好了？为什么还要耗费脑力思考在什么时候滑动缩小区间去找目标呢？
假设现在有一个有序数组arr，我们想要找到目标值target，如果找到返回目标值下标，找不到返回false
const arr = [10,11,15,17,20,27,66,100,102],
target = 102;我们先来看看遍历写法:
const arr = [10,11,15,17,20,27,66,100,102],
target = 102;
function traverse(arr) {
const len = arr.length;
let ans = false;
for (let i = 0; i < len; i++) {
if (arr[i] === target) {
return i;
}
}
return ans;
}
const res = traverse(arr);
console.log(res); // 8虽然这是个小数据，但是不难计算出在大量数据下，遍历的平均时间复杂度是 O(n)（注意：时间复杂度只有在大数据，也就是趋于无穷的时候有意义）
我们可以看看这个例子中，遍历查找了多少个元素
let count = 0;
// ...code
for (let i = 0; i < len; i++) {
count++;
if (arr[i] === target) {
return i;
}
}
// ...code
console.log(count); // 9可以看到在这个例子中，遍历查找了9个元素，进行了9次与目标值的对比
那我们来用二分查找算法解决下这题（后面会详细介绍二分查找的写法，现只用体会为什么要用二分查找）
const arr = [10,11,15,17,20,27,66,100,102],
target = 102;
// 用于计算此方法查找了多少个元素（即关键执行步数）
let count = 0;
// 二分查找实现
function binarySearch(arr) {
let left = 0,
right = arr.length - 1,
ans = false;
while (left <= right) {
count++;
const mid = Math.floor(left + (right - left)/2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
console.log(binarySearch(arr)); // 8，成功返回目标元素下标
console.log(count); // 查找了 4 次元素可以看到，我们仅查找了 4 次元素便找到了目标值。通过这个例子我们便很容易知道我们为什么要用二分查找了，因为它相对来说平均查找次数少，也就是说它的时间消耗更少，平均时间复杂度低。
我们来计算一下它的时间复杂度：
假设有一个趋于无穷的规模N，同时假设现在是个极端情况：在最后一次找到目标值或者说一直找不到。我们可以轻易列出它每次查找的值：
N、1/2N、1/4N、1/8N……1、0不难算出：
2^n= N所以我们的时间复杂度应该是：
O(log_2n) => O(logn)二分查找的思路
要想实现一个算法，我们必须先确定思路，要想确定思路，我们必须确定算法的思想。上文已经点出了二分查找的实现思想：不断查找区间的中间值（当然你也可以查找1/3，只要满足划分出来的区间等份就行，不过还是查找1/2比较好，可以减少不必要的思考量），通过中间值与目标值间的关系缩小区间，以此往复知道找到目标值或结束查找。
明确了思想接下来就是确定思路
二分查找有两大思路：
- 从循环体中查找答案
- 排除必定没有答案的区间从而确定目标所在区间（即排除法）
从循环体中查找答案
这一思路其实是非常好理解的，当前的中间值等于目标值时便找到答案。若当前中间值是小于目标值，则通过移动区间左端点的位置缩小区间。若当前中间值是大于目标值时，则通过移动我区间右端点缩小区间。所以在一开始的时候，区间的左端点便是数组的头下标0，区间的右端点便是数组的尾下标length - 1。区间的确定其实是数组中双指针思想的对撞指针。
JavaScript实现大体算算法：
// 假定给定的是一个有序数组：arr, 目标值是：target
let left = 0,
right = arr.length - 1;
// 当左指针大于右指针的时候退出循环体或者找到答案时直接退出循环体返回答案。若退出循环体时仍未找到答案则说明数组中没有答案
while (left <= right) {
// 确定每次循环的中间值的下标，请思考为什么要用 left + (right-left)/2 这种写法而不使用 (left+right)/2这种写法
const mid = Math.floor(left + (right - left)/2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] > target) {
// arr[mid] 大于 target 说明数组后半部分必定没有目标值，所以让右端点前移以达到缩小区间的目的
right = mid - 1;
} else {
// 说明目标值在数组的后半部分，所以左端点前移以达到缩小区间的目的
left = mid + 1;
}
}为什么要用left + (right - left)/2 这样的写法确定中间值呢？因为如果我们数字很大的话，直接(left +right)/2 的话，left +right 会导致数据溢出。
来道题练习一下吧：二分查找
题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// nums.sort((a, b) => a - b);
let left = 0,
right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left)/2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};思路：
首先，拿到这题一看是个升序数组，然后要找目标值一下就确定了二分查找这个写法，可以注意到，在函数体的顶部我写了这样一个注释：nums.sort((a, b) => a - b)
这是通过 JS 中数组的内置方法sort 实现的排序，在很多语言中都有这样的内置方法，一般解算法题没有明确告知要用某种排序方法来实现排序时，我们直接用内置函数实现排序即可，这也是允许的，我们只用关心核心的算法即可。
还有个我们在无要求状态下最好使用内置方法的原因是，内置方法实现的排序并不是我们单个的某种排序方法实现的（例如：冒泡、选择、快排等），它是靠一种名叫TimSort 的混合排序方案，根据我们数据量的大小决定内核采用什么排序，这样能够保证一定的性能及稳定性。
相关链接：
1、了解TimSort：https://www.jianshu.com/p/892ebd063ad9
2、JavaScript内置方法sort的实现：https://cloud.tencent.com/developer/article/1391643
这题还有一个要说的点是由于 JavaScript 是一个弱类型语言，所以为了确保数组下标不会出现小数的情况，我们必须得对下标中间值进行一个取整处理，这里是采用Math.floor 内置方法实现向下取整
看到这里稍微休息一下吧，刷刷相关的力扣题吧 :-)
猜数字大小
搜索插入位置
下一节将会介绍二分查找的第二种思路，也是二分查找最大的难点：排除法确定区间
如果觉得这篇文章对你有帮助，想要看更多相关算法内容，可以关注下我的这个新项目（https://github.com/Unicorn-NightFury/The-sword-of-algorithm）啦，会持续更新的！
喜欢的话请给我这个项目点个 Star 吧！这对我很重要！
没有评论