现在，让我们来谈谈搜索算法。回顾一下之前章节所实现的算法，我们会发现BinarySearch Tree类的search方法（第8章），以及LinkedList类的indexOf方法（第5章）等，都是搜索算法，当然，它们每一个都是根据其各自的数据结构来实现的。所以，我们已经熟悉两个搜索算法了，只是还不知道它们“正式”的名称而已。
10.2.1 顺序搜索
顺序或线性搜索是最基本的搜索算法。它的机制是，将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法。
以下是其实现：
this.sequentialSearch = function(item){ for (var i=0; i<array.length; i++){ //{1} if (item === array[i]) //{2} return i; //{3} } } return -1; //{4}}; 顺序搜索迭代整个数组（行{1}），并将每个数组元素和搜索项作比较（行{2}）。如果搜索到了，算法将用返回值来标示搜索成功。返回值可以是该搜索项本身，或是true，又或是搜索项的索引（行{3}）。如果没有找到该项，则返回-1（行{4}），表示该索引不存在；也可以考虑返回false或者null。
假定有数组[5, 4, 3, 2, 1]和待搜索值3，下图展示了顺序搜索的示意图：
10.2.2 二分搜索
二分搜索算法的原理和猜数字游戏类似，就是那个有人说“我正想着一个1到100的数字”的游戏。我们每回应一个数字，那个人就会说这个数字是高了、低了还是对了。
这个算法要求被搜索的数据结构已排序。以下是该算法遵循的步骤。
(1) 选择数组的中间值。
(2) 如果选中值是待搜索值，那么算法执行完毕（值找到了）。
(3) 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找。
(4) 如果待搜索值比选中值要大，则返回步骤1并在选种值右边的子数组中寻找。
以下是其实现：
this.binarySearch = function(item){ this.quickSort; //{1} var low = 0, //{2} high = array.length - 1, //{3} mid, element; while (low <= high){ //{4} mid = Math.floor((low + high) / 2); //{5} element = array[mid]; //{6} if (element < item) { //{7} low = mid + 1; //{8} } else if (element > item) { //{9} high = mid - 1; //{10} } else { return mid; //{11} } } return -1; //{12}}; 开始前需要先将数组排序，我们可以选择任何一个在10.1节中实现的排序算法。这里我们选择了快速排序。在数组排序之后，我们设置low（行{2}）和high（行{3}）指针（它们是边界）。
当low比high小时（行{4}），我们计算得到中间项索引并取得中间项的值，此处如果low比high大，则意思是该待搜索值不存在并返回-1（行{12}）。接着，我们比较选中项的值和搜索值（行{7}）。如果小了，则选择数组低半边并重新开始。如果选中项的值比搜索值大了，则选择数组高半边并重新开始。若两者都是不是，则意味着选中项的值和搜索值相等，因此，直接返回该索引（行{11}）。
给定下图所示数组，让我们试试看搜索2。这些是算法将会执行的步骤：
第8章中，我们实现的
BinarySearchTree类有一个search方法，和这个二分搜索完全一样，只不过它是针对树数据结构的。