現在，讓我們來談談搜索算法。回顧一下之前章節所實現的算法，我們會發現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方法，和這個二分搜索完全一樣，只不過它是針對樹數據結構的。