共计 1326 个字符，预计需要花费 4 分钟才能阅读完成。

1. 二分查找的思想
二分查找是一种使用十分普遍的查找算法，其基本的思路也非常的简单，在一个有序的数据集合中，我们想要查找某个数据，直接取最中间的那个数据，将它和要找的数据进行比较，如果较大，则在更大的那个数值区间继续取中间值查找，反之亦然。
例如我们要在一个有序的集合里 [1，3，5，6，7，8，10]，查找 5 这个值，那么二分查找的过程就如下图所示，经过三次查找操作就能够找到。

2. 二分查找的实现
相信你已经能够理解二分查找的思路了，接下来看看它的代码实现。其实根据思路不难看出，二分查找有点分治的思想，所以代码可以用递归实现，也可以用循环实现。
二分查找的递归实现：
public class BinarySearch {

public static int binarySearchByRecursion(int[] data, int value) {
return binarySearchInternally(data, 0, data.length – 1, value);
}

private static int binarySearchInternally(int[] data, int low, int high, int value) {
while (low <= high){
// 计算中间值
int mid = low + ((high – low) >> 1);

if (data[mid] == value) return mid;
else if (data[mid] < value) return binarySearchInternally(data, mid + 1, high, value);
else return binarySearchInternally(data, low, mid – 1, value);
}
return -1;
}
}
二分查找循环实现：
public static int binarySearchByCircle(int[] data, int value) {
int low = 0;
int high = data.length – 1;

while (low <= high){
// 计算中间值
int mid = low + ((high – low) >> 1);
if (data[mid] == value) return mid;
else if (data[mid] < value) low = mid + 1;
else high = mid – 1;
}
return -1;
}
3. 二分查找的局限性
二分查找是一种很高效的算法，时间复杂度为 O(logn)，要是使用上的话，非常的方便。但是，二分查找对数据的要求也十分严苛。
首先，二分查找只适用于顺序表结构，说简单点，就是数组。因为可以利用数组下标访问的特性，快速取出数据进行比较。其他的数据结构例如链表，如果使用二分查找的话，不能进行下标访问，每次比较都必须遍历链表寻找中间节点，时间复杂度就很高了。
其次，二分查找针对的是有序数组，如果数据未排序，则必须进行排序才能够使用，前面说到了，排序的时间复杂度一般为 O(nlogn)。所以，二分查找较适用于一次排序，多次查找的数据。如果数据的插入和删除操作过于频繁，那么维护有序的成本就很高。
最后，二分查找适用于数据量较大的场景，假如我们要在几十或者几百个数据中进行查找，那直接遍历查找即可。面对大量的数据，二分查找方能体现其优势。

共计 1184 个字符，预计需要花费 3 分钟才能阅读完成。

二分查找是搜索算法中的一种，用来搜索有序数组
二分查找：是一种简单算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回 null。
Javascript ES6 实现
/**
* 函数 binarySearch 接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个
函数将返回其位置。你将跟踪要在其中查找的数组部分—— 开始时为整个数组。
*/
const binarySearch = (list, item) => {
// 数组要查找的范围
// low、high 用于跟踪要在其中查找的列表部分
let low = 0
let high = list.length – 1

while(low <= high) {// 只要范围没有缩小到只包含一个元素
const mid = Math.floor((low + high) / 2)
const guess = list[mid] // 找到中间的元素

if(guess === item) {// 找到元素
return mid
}
if(guess > item) {// 猜测的数大了
high = mid – 1
} else {// 猜测的数小了
low = mid + 1
}
}

return null
}

const myList = [1, 3, 5, 7, 9]

console.log(binarySearch(myList, 3))
console.log(binarySearch(myList, -1))
运行时间：

二分查找的运行时间为对数时间（或 log 时间）。如果列表包含 100 个元素，最多要猜 7 次；如果列表包含 40 亿个数字，最多需猜 32 次。即：2的7次方 = 100
简单查找时间是 y= ax 的线性方方程所以很容易得出结论
随着元素数量的增加（x增加），二分查找需要的时间（y）并不多，而简单查找需要的时间（y）却很多。因此，随着列表的增长，二分查找的速度比简单查找快得多。
为检查长度为 n 的列表，二分查找需要执行 log n 次操作。使用大 O 表示法，这个运行时间怎么表示呢？O(log n)。一般而言，简单算法的大 O 表示法像下面这样
大 O 符号
大 O 符号中指定的算法的增长顺序

以下是一些最常用的 大 O 标记法 列表以及它们与不同大小输入数据的性能比较。

O(log n)，也叫对数时间，这样的算法包括二分查找
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n * log n)，这样的算法包括快速排序——一种速度较快的排序算法。

, 这样的算法包括选择排序——一种速度较慢的排序算法
O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法

小结

算法的速度指的并非时间，而是操作数的增速。
谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
算法的运行时间用大 O 表示法表示。
O(log n) 比 O(n) 快，当需要搜索的元素越多时，前者比后者快得越多

参考
算法图解 JavaScript 算法与数据结构