[Python]単純探索vs二分探索

1.単純探索vs二分探索

ソートされた奇数のリストを対象に目的の数字をそれぞれの探索で何秒かかるか計算します。単純探索と二分探索で実際に何秒かかるか見てみます。

2.コード

from time import time

#二分探索
def binary_search(search_list, target):
    search_min_index = 0
    search_max_index = len(search_list) - 1
    while search_min_index <= search_max_index:
        mid_index = (search_min_index + search_max_index) // 2
        guess = search_list[mid_index]
        if guess == target:
            return mid_index
        elif guess > target:
            search_max_index = mid_index - 1
        elif guess < target:
            search_min_index = mid_index + 1
    return None

#単純探索
def noraml_search(search_list, target):
    for index in range(len(search_list)):
        guess = search_list[index]
        if guess == target:
            return index
    return None

#10 * 100000個の奇数
test_list = [2 * i + 1 for i in range(10 * 100000)]
if __name__ == "__main__":
    #二分探索
    start_bsearch_time = time()
    binary_search(test_list, 1997017)
    end_bsearch_time = time()
    result_bsearch_time = end_bsearch_time - start_bsearch_time
    #単純探索
    start_nsearch_time = time()
    noraml_search(test_list, 1997017)
    end_nsearch_time = time()
    result_nsearch_time = end_nsearch_time - start_nsearch_time
    print(f"二分探索 {result_bsearch_time}[s]\n単純探索 {result_nsearch_time}[s]")

3.実行結果

二分探索 2.3126602172851562e-05[s]
単純探索 0.07646417617797852[s]