基本的な検索アルゴリズムの2分探索

問題

基本的な検索アルゴリズムの2分探索問題にチャレンジする。2分探索は、ソート済のリストに対して、検索範囲を狭めながら探索を行っていくアルゴリズム。2分探索は再帰で実装する方法もあるので、それはまた今度。

実装

アルゴリズムとしては、リストの中心の要素の値と検索値を比較し、中心の値よりも検索値が大きければ、中心から右側を探索範囲に変更し、中心の値よりも検索値が小さければ、中心から左側を探索範囲に変更することで、毎回探索範囲を狭めていく。

from typing import List

def binary_search(numbers: List[int], target: int) -> int:
    left, right = 0, len(numbers) - 1

    while left <= right:
        center = (left + right) // 2
        if numbers[center] == target:
            return center
        elif numbers[center] < target:
            left = center + 1
        else:
            right = center - 1
    return -1



if __name__ == '__main__':
    numbers = [5,7,15,28,29,31,39,58,68,70,95]
    print(binary_search(numbers, 68))

8

リストの中心の要素の値と検索値を比較し、中心の値よりも検索値が大きければ、中心から右側を探索範囲に変更し、中心の値よりも検索値が小さければ、中心から左側を探索範囲に変更するという過程を表示すると、このようになる。

from typing import List

def binary_search_show(numbers: List[int], target: int) -> int:
    left, right = 0, len(numbers) - 1

    print('   |', end='')
    for i in range(len(numbers)):
        print(f'{i:4}', end='')
    print()
    print('---+' + (4 * len(numbers) + 2) * '-')

    while left <= right:
        center = (left + right) // 2

        # for display start
        print('   |', end='')
        if left != center:
            print((left * 4 + 1) * ' ' + '< ' + ((center - left) * 4) * ' ' + '+', end='')
        else:
            print((center * 4 + 1) * ' ' + '<+', end='')
        if center != right:
            print(((right - center) * 4 - 2) * ' ' + ' >')
        else:
            print('>')
        print(f'{center:3}|', end='')
        for i in range(len(numbers)):
            print(f'{numbers[i]:4}', end='')
        print('\n   |')
        # for display end

        if numbers[center] == target:
            return center
        elif numbers[center] < target:
            left = center + 1
        else:
            right = center - 1
    return -1


if __name__ == '__main__':
    import random
    nums = [49,94,110,124,138,275,303,377,439,547,569,584,669,742,787,788,853,857,864,992]
    print(binary_search_show(nums, 853))


   |   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19
---+----------------------------------------------------------------------------------
   | <                                     +                                       >
  9|  49  94 110 124 138 275 303 377 439 547 569 584 669 742 787 788 853 857 864 992
   |
   |                                         <                 +                   >
 14|  49  94 110 124 138 275 303 377 439 547 569 584 669 742 787 788 853 857 864 992
   |
   |                                                             <         +       >
 17|  49  94 110 124 138 275 303 377 439 547 569 584 669 742 787 788 853 857 864 992
   |
   |                                                             <+   >
 15|  49  94 110 124 138 275 303 377 439 547 569 584 669 742 787 788 853 857 864 992
   |
   |                                                                 <+>
 16|  49  94 110 124 138 275 303 377 439 547 569 584 669 742 787 788 853 857 864 992
   |
16

再帰関数での実装

2分探索を再帰関数で実装する方法にチャレンジする。インナー関数として2分探索を実装し、インナー関数を呼び出せば2分探索の再帰関数を使った実装は完了。インナー関数の先頭に_をつけるのはPythonの作法？とも聞いた。

from typing import List

def binary_search_recur(numbers: List[int], target: int) -> int:

    # inner function
    def _binary_search(numbers: List[int], target: int, left: int, right: int) -> int:
        if left > right:
            return -1

        center = (left + right) // 2
        if numbers[center] == target:
            return center
        elif numbers[center] < target:
            return _binary_search(numbers, target, left = center + 1, right = right)
        else:
            return _binary_search(numbers, target, left = left, right = center - 1)

    return _binary_search(numbers, target, left = 0, right = len(numbers) - 1)

if __name__ == '__main__':
    nums = [49,94,110,124,138,275,303,377,439,547,569,584,669,742,787,788,853,857,864,992]
    print(binary_search_recur(nums, 853))

16

これもぱっと見ただけだど理解しにくいので、図解してイメージを持っておく。