二分查找算法

背景

今天，小郑和小明还有小红在玩一个猜数字的游戏，小红做庄。游戏的规则是参赛选手每人三次机会，如果参赛选手用完三次机会后，还没有猜中数字，他们就要请做庄的人吃棒棒糖，如果他们猜中了，坐庄的人请他们吃棒棒糖。

现在游戏开始，有请小红同学写下一个数字在便利贴上。小红若有期待地在便利贴上写下了97。

小明：50，对吗?

小红：不对, 偏小

小郑：75, 可还行？

小红：哈哈，错啦，偏小

小明：87，对吗？

小红：你又错了，偏小

小郑：93, 对吗？

小红：差一点哦，偏小

小明：是不是96？

小红：好可惜啊，你没有机会了，请吃棒棒糖吧。

小郑若有所思地回答：97

小红：哇，你好棒啊，走我们去吃棒棒糖吧。

从楼上这个例子，我们可以抽出一个模型。给定一组有序排列的数组，每次将目标值和靠近范围中间的值进行比较，如果偏大就把中间值给左边范围再从新的范围中间值找，如果偏小就把中间值给右边范围再从新的范围中间值找，如果找到了我们返回其数组下标对应的索引，如果没有找到我们就返回-1。形如这样的一种查找方法，我们将其称之为“二分查找”。

实现一个二分查找算法

leetcode上有一题关于二分查找的题目，我们就以这个为例来实现一个二分查找。

题目描述

给定一个 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

示例3

输入：nums=[2, 5], target=2

输出：0，

解释：2出现在nums中并且下标为0

提示：

你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。

这里的提示对审题很有帮助，第一句话，它告诉你叫你放心这些数据都是不重复的，你放心写最简单那种写法，第二句话，告诉你撑死也就10000个数字，数据量还算好的，第三句话，告诉你不用担心整型的范围会溢出、而且这里是有符号的整型。所以提示还是很有帮助的，虽然不一定能够体现在代码上。

思路

我们先分析下二分查找干了件什么事？无非就是在一个范围内取中间那位和目标元素进行比大小，如果没有恰好等于目标元素，我就继续选择两段其中的一段继续劈它，直到劈到还剩下最后一个元素。所以显而易见的我们需要一个while循环来帮助我们做这样一件事。第二件事我们就要思考了，这个while循环成立的条件是什么？总不能搞个死循环吧。当左边标志位的小于等于右边标志位的时候，我们继续循环。这里小于大家可能很好理解，那么等于是什么情况呢。我们就举一举示例3的例子，当我想要找到5这个数的时候，第一次left=mid=0, right=1,这个时候我们发现偏小，然后如果不取等号的情况下，我们就退出啦，所以这里加上等号，第二次left=right=1的时候，刚好找到它。紧接着我们思考第三件事情，我取哪一半呢？这个时候就需要对于中间那位和目标那位两者的大小了，如果偏大我就把中间那位减去1赋值给right，如果偏小，那么我就把中间那位加1赋值给left，然后重新计算中间那位再次进行比较。好，接下来我们一起码一码。

代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  var left = 0;
  var right = nums.length - 1;
  var mid = left + Math.floor((right - left) / 2);
  while(left <= right) {
    if (target > nums[mid]) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else if (target === nums[mid]) {
      return mid;
    }
    mid = left + Math.floor((right - left) / 2);
  }
  return -1;
};

问题思考

二分查找的时间复杂度是多少？

先说答案，O(logn), 大致的推到流程是，n(1/2)^k = 1, 倒推下k = log2n, 反应到计算机上的时间复杂度就是logn

二分查找适用的场景是什么？

面试刷人(因为容易写错)，数据量中等，且数据不溢出范围，最重要的是一组排好序的数进行二分查找。

就拿我们上面最开头的例子讲，普通的查找要97次，而用了二分查找的思想6次了，这不是很香嘛。

参考文献

704.二分查找(leetcode): https://leetcode-cn.com/problems/binary-search/