AT's Blog

趣味のプログラミングに関する技術メモがメインです。

【Python】【アルゴリズム】二分探索法(バイナリサーチ)

息抜きにアルゴリズムの勉強を始めました。

アルゴリズムを、はじめよう」では、以下のアルゴリズムフローチャートと擬似言語を使って噛み砕いて説明してくれます。

  1. 線形探索法(リニアサーチ)
  2. 二分探索法(バイナリサーチ
  3. ハッシュ探索法
  4. 単純交換法(バブルソート
  5. クイックソート
  6. エラトステネスのふるい
  7. ユークリッドの互除法
  8. 単純選択法(選択ソート)
  9. 単純挿入法(挿入ソート)

実際のプログラミング言語を用いた説明はないので、Pythonで実装しながら読み進めていこうと思います。

線形探索法(リニアサーチ)

  • 0~9までの整数が昇順で並んだリストから、引数で指定された整数をリニアサーチします。

linear_search.py

import sys

ls = list(range(0,10))
target = int(sys.argv[1])

for x in ls:
    if(x == target):
        print("I found ", target, "!", sep='')
        sys.exit()
    else:
        print(x)

print("I couldn't find ", target, ".", sep='')
>python linear_search.py 8 
0
1
2
3
4
5
6
7
I found 8!
>py linear_search.py 11
0
1
2
3
4
5
6
7
8
9
I couldn't find 11.

二分探索法(バイナリサーチ

  • 0~9までの整数が昇順で並んだリストから、引数で指定された整数をバイナリサーチします。
  • イナリサーチの過程がわかるように書いてみました。

binary_search.py

import sys

ls = list(range(0,10))

head = 0
tail = len(ls)-1

target = int(sys.argv[1])

print("target:", target)

while(head <= tail):
    print("head:", head)
    print("tail:", tail)


    print(ls[head:tail+1])

    center = int((head+tail)/2)
    print("center:", center)
    
    if(ls[center] == target):
        print("I found ", target, "!", sep='')
        exit()
    elif ls[center] < target:
        head = center + 1
    else:
        tail = center - 1
    print()
    
print("I couldn't find ", target, ".", sep='')
>python binary_search.py 5
target: 5
head: 0
tail: 9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
center: 4

head: 5
tail: 9
[5, 6, 7, 8, 9]
center: 7

head: 5
tail: 6
[5, 6]
center: 5
I found 5!