iT邦幫忙

2021 iThome 鐵人賽

DAY 16
0
自我挑戰組

每日攝取一點資料結構和演算法系列 第 16

Day16:[搜尋演算法]Binary search - 二分搜尋法

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20210916/20128604sv41SWmjvV.jpg

利用將資料切一半的方式來做搜尋,舉例來說,如果要從數字1–100猜終極密碼,如果採用線性搜尋法就是一個一個問?是1嗎?是2嗎?…依序猜下去,很不幸的數字剛好是99就需要猜99次,但如果用二分搜尋法就會是先判斷數字是否大於50 ,如果是的話那是否大於75 ,依此類推每次都用對半砍的方式縮小範圍,最後只需要猜七次就能猜出終極密碼。

https://ithelp.ithome.com.tw/upload/images/20210916/2012860482dkx8TMGB.png
每次都將搜尋範圍縮減1/2

使用二分搜尋法的前提必須是先排序過

假設目前有個陣列:[10, 21, 34, 50, 66,79, 82, 97],要找出陣列中是否有79這個數字,有的話就回傳79在哪個index

這邊運用到雙指針的概念來解題(left, right),關於雙指針的說明可以參考這篇文章, 這裡可以先想像有兩個指針會不斷往中間靠攏,進而縮短搜尋區間。

實作的概念為:

  1. 先在陣列取一個中間數的index,公式為 Math.floor((left+right)/2),0+7除以2無條件捨去後拿到3,這邊用middle標示為中間數。
    https://ithelp.ithome.com.tw/upload/images/20210916/20128604Qqw9MeHAz2.png
    上方黃色小字為index2

  2. 這時拿目標數79去跟中間數50比較,目標數79比較大,代表中間數的左邊那堆數字都不可能是我們要找的答案(都太小了),所以我們要調整一下搜尋範圍,將left指針移動到middle+1的位置。

為甚麼要middle+1?因為已經知道middle不是答案,搜尋範圍就可以排除middle了
https://ithelp.ithome.com.tw/upload/images/20210916/20128604Km7NKDK2Ry.png

  1. 重新計算中間數,(4+7)/2無條件捨去算出5,而在index 5的數字79就是我們要找的數字。
    https://ithelp.ithome.com.tw/upload/images/20210916/20128604Gzl5anonvg.png

用js實作二分搜尋法

時間複雜度

  • 在最差的情況下, 時間複雜度是O(log n)
  • 在最佳的情況下 , 時間複雜度是O(1)
  • 在平均情況下,時間複雜度為 O(log n)

上一篇
Day15:[搜尋演算法]Linear Search - 線性搜尋法
下一篇
Day17:[排序演算法]Selection Sort - 選擇排序法
系列文
每日攝取一點資料結構和演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言