一、基础概念

1、Sorted（单调递增or单调递减）

2、Bounded(存在上下界)

3、Accessible by index（能够通过索引访问，数组适合，but链表不适合）

二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。

二分查找一般由三个主要部分组成：

1、预处理--如果有集合未排序，则进行排序。

2、二分查找--使用循环或递归在每次比较后将查找空间划分为两半

3、后处理--在剩余空间中确定可行的候选者

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

提示：

1、你可以假设 nums 中的所有元素是不重复的。

2、n 将在 [1, 10000]之间。

3、nums 的每个元素都将在 [-9999, 9999]之间。

step01: 设定初始值 left和 right：

step02: 设定中间指针 mid = left + (right-left)/2：

step03：

step04：

step05：

step06：

step07：

二、通用模版

2.1 模版一

var binarySeach(nums,target){
  if(nums == null|| nums.length ==0){
    return -1;
  }
  let left =0,right=nums.length- 1; //初始条件
  while(left<=right){ //终止条件 left>right
    let 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;
}

关键属性：

• 二分查找的最基础和最基本的形式
• 查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）
• 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则指导未找到该元素。

2.2 模版二

var binarySeach(nums,target){
  if(nums == null|| nums.length ==0){
    return -1;
  }
  
  let left =0,right=nums.length; //初始条件
  
  while(left<right){ //终止条件 left>=right
    let mid = Math.floor(left + (right-left)/2);  //阻止(left+right)溢出
    if(nums[mid] == target){ 
      return mid;
    } else if(nums[mid]<target){
      left = mid + 1; //向右查找
    }else{
      right = mid; //向左查找
    }
  }
  if(left !=nums.length && nums[left] == target) return left;
  return -1;
}

模版二：是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。

关键属性：

• 一种实现二分查找的高级方法
• 查找条件需要访问元素的直接右邻居
• 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右
• 保证查找空间在每一步中至少有2个元素
• 需要进行后处理，当你剩下一个元素的时候，循环/递归结束。需要评估剩余元素是否符合条件

2.3 模版三

var binarySeach(nums,target){
  if(nums == null|| nums.length ==0){
    return -1;
  }
  
  let left =0,right=nums.length-1; //初始条件
  
  while(left+1 < right){ //终止条件 left+1 == right
    let mid = Math.floor(left + (right-left)/2);  //阻止(left+right)溢出
    if(nums[mid] == target){ 
      return mid;
    } else if(nums[mid]<target){
      left = mid; //向右查找
    }else{
      right = mid; //向左查找
    }
  }
  if(nums[left] == target) return left;
  if(nums[right] == target) return right;
  return -1;
}

模版3是二分法查找的另一种独特形式。 它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

关键属性：

• 实现二分法查找的另一种方法
• 搜索条件需要访问元素的直接左右邻居
• 使用元素的邻居来确定它是向右还是向左
• 保证查找空间在每个步骤中至少有3个元素
• 需要进行后处理。当剩下2个元素，循环/递归结束。

2.4、模版分析：

这三个模版的不同之处在于：

• 左、中、右索引的分配
• 循环或递归终止条件
• 后处理的必要性

其中模版一和模版三是最常用的， 几乎所有二分查找问题都可以用其中之一亲送实现。 模版二更高级一些， 用于解决某些类型的问题。

这 3 个模板中的每一个都提供了一个特定的用例：

模板 1 (left <= right)

• 二分查找的最基础和最基本的形式。
• 查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
• 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

模板 2 (left < right)

• 一种实现二分查找的高级方法。
• 查找条件需要访问元素的直接右邻居。
• 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
• 保证查找空间在每一步中至少有 2 个元素。
• 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

模板 3 (left + 1 < right)

• 实现二分查找的另一种方法。
• 搜索条件需要访问元素的直接左右邻居。
• 使用元素的邻居来确定它是向右还是向左。
• 保证查找空间在每个步骤中至少有 3 个元素。
• 需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。

三、复杂度计算

3.1、时间复杂度

O(log n) ：

因为二分查找是通过对查找空间中间的值应用一个条件来操作的，并因此将查找空间折半，在更糟糕的情况下，我们将不得不进行O(log n) 次比较， 其中n是集合中元素的数目。

为什么是log n?

• 二分查找是通过将现有数组一分为二来执行的
• 因此，每次调用子例程（或完成一次迭代）时，其大小都会减少到现有部分的一半。
• 首先N变成 N/2，然后又变成N/4，然后继续下去，直到找到元素或尺寸变为1。
• 迭代的最大次数是log N(base2)。

第一次： n/2
第二次： n/2^2
第三次： n/2^3
...
第k次： n/2^k

3.2、空间复杂度

O(1)

虽然二分查找确实需要跟踪 3 个指标，但迭代解决方案通常不需要任何其他额外空间，并且可以直接应用于集合本身，因此需要 O(1) 或常量空间。

四、二分查找的应用

• 二分调试法

把所有潜在的问题都用类似“数组二分查找”的方式把代码遍历一遍，不断缩小问题的范围，最终找到问题原因。

通过二分法，我们可以快速缩小问题范围，这样一来调试的效率也就上去了。

• Kafka 采用二分法找数据

二分查找相关系列题：