二分查找（Binary Search

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

时间复杂度 O(logn)

被查找区间的大小变化：n、n/2、n/4、n/8…n/2^k

O(logn) 对数时间复杂度。这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效。
因为 logn 是一个非常“恐怖”的数量级，即便 n 非常非常大，对应的 logn 也很小

我们前面讲过，用大 O 标记法表示时间复杂度的时候，会省略掉常数、系数和低阶。对于常量级时间复杂度的算法来说，O(1) 有可能表示的是一个非常大的常量值，比如 O(1000)、O(10000)。所以，常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高。

反过来，对数对应的就是指数。有一个非常著名的“阿基米德与国王下棋的故事”，指数时间复杂度的算法在大规模数据面前是无效的。

被查找区间

二分查找的思路

有序的元素列表，如果要查找的元素包含在列表中，返回其位置，否则返回null

function secodeSearch(arr,target){
    // 二分查找
    let low=0, high, mid
    if(Array.isArray(arr)){
        high= arr.length - 1
    }
    // 只要范围没有缩小到只含一个元素
    while(low <= high){
        mid= Math.round((low+high)/2)
        if(arr[mid] == target) return mid
        if(arr[mid] < target){
            low= mid + 1
        }else{
            high= mid - 1
        }
    }
    return -1
}
console.log(secodeSearch([1,2,3,4], 5))

注意的地方

循环退出条件：low<=high
mid 的取值

mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是 mid = low+(high-low)/2。如果要将性能优化到极致的话，可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。
low 和 high 的更新

递归实现二分查找

// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;

  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}

二分查找应用场景的局限性

二分查找依赖的是顺序表结构(数组)，需要借助于下标
二分查找针对的是有序数据
数据量太小/太大不适合二分查找

二分查找底层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，直接使用顺序遍历就可以了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

虽然大部分情况下，用二分查找可以解决的问题，用散列表、二叉树都可以解决。但是不管是散列表还是二叉树，都会需要比较多的额外的内存空间。

求一个数的平方根（精确到小数点后6位）

根据x的值，判断求解值y的取值范围
假设求解值范围min < y < max。
若0<x<1，则min=x，max=1，
若x=1，则y=1，
x>1，则min=1，max=x，
在确定了求解范围之后，利用二分法在求解值的范围中取一个中间值middle=(min+max)÷2，判断middle是否是x的平方根
若(middle+0.000001)*(middle+0.000001)＞x且(middle-0.000001)*(middle-0.000001)<x，
根据介值定理，可知middle既是求解值。
若middle*middle > x，表示middle＞实际求解值，max=middle;
若middle*middle ＜ x，表示middle＜实际求解值，min =middle;之后递归求解！
备注：因为是保留6位小数，所以middle上下浮动0.000001用于介值定理的判断

low = 0
   mid = x / 2
   high = x
   while abs(mid ** 2 - x) > 0.000001:
       if mid ** 2 < x:
           low = mid
       else:
           high = mid
       mid = (low + high) / 2
   return mid

二分查找的变形问题

查找第一个值=给定值的元素
查找最后一个值=给定值的元素
查找第一个值>=给定值的元素
查找第一个值<=给定值的元素

中间元素与要查找元素有三种关系：大于、小于、等于。在等于的时候做特殊判断

查找第一个，可以比较mid-1位置的元素和target的关系。查找最后一，比较mid+1位置元素与target的关系

查找第一个值等于给定值的元素

一个有序数组，其中，a[5]，a[6]，a[7] 的值都等于 8，查找第一个等于 8 的数据，也就是下标是 5 的元素。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

查找最后一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

查找第一个大于等于给定值的元素

3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6。

public int bsearch(int[] a, int n, int value) {
  int low = 0; 
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

查找最后一个小于等于给定值的元素

3，5，6，8，9，10。最后一个小于等于 7 的元素就是 6。

public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

关于二分查找的题目还有挺多的：

旋转数组中找最小值
在旋转数组中找指定值等等