寫程式前就該懂的演算法-筆記(一)

開始之前

在工作生涯的一段奇特空檔,曾經認真地嘗試了一段時間,那時左腳還打著石膏,還是去學了以前念書期間很殘念的java.lang,最終迫於現實加上運氣好,不知怎麼地又回到了老本行工作,偶然在網路上的廣告上看到grokking algorithm這本書,覺得很適合自己,翻譯本過了幾週就出現在網路書店的推薦列表,倒省了每個月挑哪本書買的猶豫,只是買是買了,總是沒讀完的書,最終也只是變成一堆花錢買來的紙本知識,想辦法記錄下來是不是比較有效呢? 從這裡開始試試看能堅持多久吧!

第一章 演算法概述

演算法(algorithm)是為了解決問題,完成任務而設計出來的精確步驟,拿料理來比喻的話就像食譜,雖然不能但可以用程式來實現,在選擇及使用演算法時需要考慮到效能以及要解決什麼樣的問題,以能實作為主要考量。

又叫二分搜尋,二元搜尋等等,從一個已排序的資料中間開始搜尋,用來加快搜尋速度。
適用的搜尋問題,例如從排序好的電話簿裡找人,從0~100裡面找特定數字。

Binary Search輸入項會是完成排序的資料或清單,找到之後傳回該資料所在的位置

例如從1~100猜一個數字

答案 99

從1開始猜,猜完就剔除,要猜99次,逐項搜尋很慢。

若一開始就從中位數50猜,在判斷較高或較低,可大幅縮減次數變成(log2 n)次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(data_list, item):
low = 0
high = len(data_list)-1

while low <= high:
mid = (low + high) // 2
guess = data_list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None

上述程式碼存成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