開始之前
在工作生涯的一段奇特空檔,曾經認真地嘗試了一段時間,那時左腳還打著石膏,還是去學了以前念書期間很殘念的java.lang,最終迫於現實加上運氣好,不知怎麼地又回到了老本行工作,偶然在網路上的廣告上看到grokking algorithm這本書,覺得很適合自己,翻譯本過了幾週就出現在網路書店的推薦列表,倒省了每個月挑哪本書買的猶豫,只是買是買了,總是沒讀完的書,最終也只是變成一堆花錢買來的紙本知識,想辦法記錄下來是不是比較有效呢? 從這裡開始試試看能堅持多久吧!
第一章 演算法概述
演算法(algorithm)是為了解決問題,完成任務而設計出來的精確步驟,拿料理來比喻的話就像食譜,雖然不能但可以用程式來實現,在選擇及使用演算法時需要考慮到效能以及要解決什麼樣的問題,以能實作為主要考量。
二進位搜尋(Binary Search)
又叫二分搜尋,二元搜尋等等,從一個已排序的資料中間開始搜尋,用來加快搜尋速度。
適用的搜尋問題,例如從排序好的電話簿裡找人,從0~100裡面找特定數字。
Binary Search輸入項會是完成排序的資料或清單,找到之後傳回該資料所在的位置。
例如從1~100猜一個數字
答案 99
從1開始猜,猜完就剔除,要猜99次,逐項搜尋很慢。
若一開始就從中位數50猜,在判斷較高或較低,可大幅縮減次數變成(log2 n)次。
用Python實作binary search
1 | def binary_search(data_list, item): |
上述程式碼存成binary_search.py,啟動Pytohn 3.6環境
執行結果
>>>data_list = [1,2,3,4,5,6,7,8,9,10]
>>>import binary_search as bs
>>>bs.binary_search(data_list, 5)
4