Pythonで学ぶアルゴリズム（07/18）

　アルゴリズムを学ぶのにPythonの学習も兼ねて

Ｐｙｔｈｏｎで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ)

を参照していく。

前回

power-of-awareness.com

5.　データの探索

5.1　配列とデータの探索

################################
### Pythonにおけるデータ探索 ###
################################

import random

random.seed(1) # 乱数シードの設定

my_array = [random.randint(0,100) for i in range(15)] # ランダムな正の整数列を生成

print(my_array) # データの中身を確認

# データを探索
print(32 in my_array) # my_array内に32が存在するか？→論理値
print(my_array.index(17)) #.index(X)でXがリストの何番目(Pythonは0番目から始まる点に注意)にあるかを返す
print(my_array.index(101)) # もし存在しない値を探索させるとValueErrorを返す

5.2　線形探索

　総当たり的にデータの有無を探索するのが線形探索である。そのため計算量は平均的には回の比較であり、最悪の場合は回の比較であるから、である。

################
### 線形探索 ###
################

# 総当たり的に値の有無を調べる
def linear_search(array, target):
    for v in array:
        if target == v:
            return True
    return False

print(linear_search(my_array, 17))
print(linear_search(my_array, 101))

5.3　二分探索

　配列がソートされているという前提ではより高速な探索方法が二分探索である。二分探索は以下のようなアルゴリズムを持つ：

• 配列の真ん中の値をポインタとする。
• ポインタの値を検索値と比較し、検索値の方が大きければ配列のポインタよりも左側の真ん中を、小さければ右側の真ん中を新たなポインタとする。
• 検索を再度繰り返し、最終的に残った配列の長さが1となった時点でその値が検索値に一致したらTrue、そうでなければFalseを返す

二分探索の計算量はである*1。二分探索での結果がだったとしても、ポインタの最終的な場所は検索値を検索対象に挿入する場合の場所を表している。

################
### 二分探索 ###
################

import bisect

my_array.sort() # ソートしておく
bisect.bisect(my_array,40)

bisect.bisect_left(my_array,40) # 検索値が存在する場合、目的の値の左側を返す
bisect.bisect_right(my_array,40) # 検索値が存在する場合、目的の値の右側を返す

# Pythonにおけるbisect_rightの実装を引用
def bisect_right(a, x ,lo =0, hi = None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        li = len(a)
    while lo < hi:
        mid = (lo + hi)//2
        if x < a(mid): hi = mid
        else: lo = mid + 1
    return lo

次回

power-of-awareness.com

*1:このときの対数の底はである。