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

發表於 | | 閱讀次數:

開始之前

在工作生涯的一段奇特空檔，曾經認真地嘗試了一段時間，那時左腳還打著石膏，還是去學了以前念書期間很殘念的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