11.二分查找的实现与特性

二分查找的前提

1. 目标函数单调性（单调递增或者递减）
2. 存在上下界（bounded）
3. 能够通过索引访问（index accessible）

这三个前提条件的话简单说来，一定要把它形成肌肉式记忆。

• 第一单调性：二分查找的是在有序的里面进行查找，如果它是无序的话记忆没法进行二分查找，无序的话怎么办呢？只能从头到尾遍历，正因为它是有序的，所以能够通过判断它的某些特征排除掉比如说前半部分或者排除掉后半部分，所以这里它必须是要单调的。
• 第二上下界：存在一个上下界，如果没有上下界的话，那么它的空间可能是无穷大的，那么它就没法往中间扩，当然也有特殊的形态。
• 第三索引：索引的话指的是可以用下标进行访问，所以很多时候如果是单链表的话，相对来说即使是有序的，单链表进行二分查找都不是那么容易的，当然如果把单链表进行一些改造，比如说用它所谓的跳表的方式，那就另当别说了。

代码模版

// Java
public int binarySearch(int[] array, int target) {
    int left = 0, right = array.length - 1, mid;
    while (left <= right) {
        mid = (right - left) / 2 + left;

        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return -1;
}

# Python
left, right = 0, len(array) - 1 
while left <= right: 
      mid = (left + right) / 2 
      if array[mid] == target: 
            # find the target!! 
            break or return result 
      elif array[mid] < target: 
            left = mid + 1 
      else: 
            right = mid - 1

C/C++

int binarySearch(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size()-1;
    
    while (left <= right) {
        int mid = left + (right - left)/ 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;
}

/* JavaScript */
let left = 0, right = len(array) - 1
while (left <= right) {
  let mid = (left + right) >> 1
  if (array[mid] === target) { /*find the target*/; return }
  else if (array[mid] < target) left = mid + 1
  else right = mid - 1
}

首先左右界，分别是 和 ，也就是左右的下标值，这个毋庸置疑，while 的话里面是 left 小于等于 right 所以这个条件的话有些时候会变成没有等于号，但是大部分情况下你可以认为是有小于等于的。

然后得到它的中间值，就是 mid 这个值，判断 mid 是否等于等于 target，然后来 break 或者是 return 这个 result，可以先把等于等于放在这里，只要它等于的话就马上 return 即可。

在这里的话我们假设是上升的就是升序排列的，如果 target 大于 array[mid] 的话说明什么？说明它在右侧，那么要继续向右查找，所以 left 就把左界向右进行移动变成 了，否则的话说明在这左侧，那么右界的话就要向左移动变成 这么一个形式。

那么根据这里所谓的左下界和右下界为整形的情况下，就是为 Integer 的情况下，在有些时候可能为实数的情况下，那么就没有所谓的加一或减一，在这个地方就直接等于 mid 即可。另外在有些特殊的情况，这里直接是小于的这种情况下，后面在例题的时候会大家一个更深刻的了解。

示例

在递增数组里
[10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
查找：

它中间有些数是不连续的，但总体是单调递增的，我们要查31这么查，如果是正常遍历的话，就是查这个一次两次三次四次五次六次查找，它的mid值算出来就等于31。那么用 二分 的话这么办呢？

二分的话首先我们要查的是31，算它的中间值，中间值刚才等于27，31 和 27 对比大于27，说明可以排除前半部分，继续从后半部分进行查找，继续查找，只要查后半部分了，前半部分白色就不用考虑了，继续在灰色部分查找。

灰色部分的中间继续算，mid 的话就等于 35，查 35 的话比 35 小就说明继续在 27 的右侧 35 的左侧开始找，就在这个数组里面开始找。它的 mid 值又算出来等于 33，它小于 33 ，再继续往左边找，最后就找到了 31 这个数。

所以它是油左右两个边界不断地向中间进行夹逼的过程，这种夹逼的过程又由于这个数组本身它是单调递增的，所以我们每次可以排除一半，你可以认为有点像二叉搜索树一样的特性，但这里的是用数组来进行实现的，而二分查找本身这种有序性的话，很多时候在数学里面的话用得也特别多，。

部分图片来源于网络，版权归原作者，侵删。