資料結構與演算法:二分查詢
二分查詢是搜尋演算法中的一種,用來搜尋有序陣列
二分查詢:是一種簡單演算法,其輸入是一個有序的元素列表(必須有序的原因稍後解釋)。如果要
查詢的元素包含在列表中,二分查詢返回其位置;否則返回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)快,當需要搜尋的元素越多時,前者比後者快得越多