テスト駆動開発の練習(11) -Python&noseで2分探索-

3日ほどネットのない実家に寄生・・・もとい帰省していたので、その間に少しばかりTDDの練習。

今回はPython&noseで2分探索を作ってみました。


2分探索はリストの探索アルゴリズムでは逐次探索の次に出てくるベーシックな探索ではないでしょうか。

早速、ソースコードを。

class BinarySearch:
    
    def __init__(self, sortedList):
        self.list = sortedList
        
    def search(self, data):       
        low = 0
        high = len(self.list)
        
        while low <= high:
            mid = int((low+high)/2)
            if self.list[mid] <= data:
                low = mid+1
            if self.list[mid] >= data:
                high = mid-1
        
        if low == high+2:
            return "%d" % mid
        else:
            return "No Exist"

BinarySearch.py

from BinarySearch import *

class TestBinarySearch:
    
    def setup(self):
        self.bsearch = BinarySearch([1, 3, 6, 9, 11, 23])
        
    def test_binarySearch(self):
        assert self.bsearch.search(1)=="0"
        assert self.bsearch.search(3)=="1"
        assert self.bsearch.search(6)=="2"
        assert self.bsearch.search(9)=="3"
        assert self.bsearch.search(11)=="4"
        assert self.bsearch.search(23)=="5"
        assert self.bsearch.search(2)=="No Exist"

testBinarySearch.py


ちなみにBinarySearchクラスのsearch()メソッドが返すのは、引数で与えられた数字が何番目に入っているです。

当たり前のことですが、上のソースコードのコンストラクタに昇順に整列していないリストを渡しても探索できないのであしからず。


py.testからnoseに切り替えた理由は、Web上で「py.testはPython 3.xに対応する気が無いらしい」という話を見てしまったため。ただ、基本的な単体テストとしての使い方をしている場合は、py.testからnoseに切り替えても大したテストコードの差異が生まれないため、乗り換えに苦労はしませんでした。