KhanAcademy – Algorithms – Binary Search

什麼是Linear Search

一一依序檢查集合中的項目,確認是否為要尋找的項目。

什麼是Binary Search

適用於在排序好的集合中找出特定項目。每次猜測的值都為可能範圍的(最大值 + 最小值) / 2,如果數值過大/小,則將最大/小值改為比該猜測值更小/大,使得可能範圍縮小一半,依此規則重複進行猜測,直到猜中為止。此外,若最小值變得比最大值還大,則代表要尋找的項目不在可能範圍之內。

O(n) = ln(n),也就是base-2 logarithm of n。

使用Psuedocode描述演算法

可以避免採用特定程式語言實作演算法時涉及較多與程式語言本身、輸入資料驗證或例外處理等相關,但與演算法本身無關的細節的問題。

本課程的Psuedocode採用英文和Javascript的組合。

廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s