二分查找，也称折半查找。利用二分思想，每次查找的时候把数据分为两半，从中间值开始找。
如上图所示，low和high代表数组的两边下标，mid代表数组的中间下标。
若目标值比中间值大，即目标值在mid与high之间，就修改low的值。再对比中间值。
若目标值比中间值小，即目标值在low与mid之间，就修改high的值。再对比中间值。
上述就是二分查找的过程，那它的时间复杂度怎么求呢?
假设数组的长度为n，那么查找一次后长度变为n/2，再查找一次后长度变为n/4,以此类推，最坏情况下，n/2^k为空，查找停止。于是我们有以下的公式：
n * n/2 * n/4 * n/8 * n/2^k ·····
以上是一个等比数列，n / 2^k = 1时，k就是查找的次数。即k=log2n，所以时间复杂度为O(logn)，这是一种非常高效率的算法。
function binary_search(arr, key) { var low = 0, high = arr.length - 1; while(low <= high){ var mid = parseInt(low + (high - low) / 2); if(key === arr[mid]){ return mid; } else if (key > arr[mid]){ low = mid + 1; } else if (key < arr[mid]){ high = mid -1; } else { return -1; } } }; var arr = [5,13,19,21,37,56,64,75,80,88,92]; var result = binary_search(arr, 21); console.log(result);
二分查找除了上边介绍的循环方法外，还可以用递归来实现。
function binary_search(arr,low, high, key) { if (low > high){ return -1; } var mid = low + ((high - low) >> 1); if(arr[mid] == key){ return mid; }else if (arr[mid] > key){ high = mid - 1; return binary_search(arr, low, high, key); }else if (arr[mid] < key){ low = mid + 1; return binary_search(arr, low, high, key); } }; var arr = [5,13,19,21,37,56,64,75,80,88,92]; var result = binary_search(arr,0, 11, 21); console.log(result);
和上边介绍的二分查找思路一样：
function binary_search(arr, key) { var low = 0, high = arr.length - 1; while (low <= high) { var mid = low + ((high - low) >> 1); if (arr[mid] > key) { high = mid - 1; } else if (arr[mid] < key) { low = mid + 1; } else { if ((mid == arr.length - 1) || (arr[mid + 1] != key)) return mid; else low = mid + 1; } } return -1; } var arr = [5,13,19,21,21,37,56,64,75,80,88,92]; var result = binary_search(arr, 21); console.log(result);
原文：https://www.cnblogs.com/magicg/p/12749445.html