Pythonで重複要素のある時の二分探索（バイナリサーチ） #Python

重複要素がある時の二分探索をpythonで作ってみました。

探索は色々な場面で使うので汎用性を持たせたようなものを作りたいと思っています。

まずは、重複要素がある時に先頭の要素を返す二分探索です。

import numpy as np

#適当なarrayを作成する
arry =  [1,2,1,2,5,3,4,3,6,7,2,8,9,7,10]
arry = np.sort(arry)

#探索したい値を指定
target = 7

#二分探索
binary_search(arry, target)
#10

#-------------------------------------------------
#2分探索
def binary_search(arry,target):
    lower = 0                               
    upper = len(arry) -1

    while lower < upper:#上限と下限が反転するまで探索
        mid = (lower + upper) // 2
        result = arry[mid]
        if arry[mid] < target:#小さければ下限を変更
            lower = mid + 1 
        else:#その他はここ
            upper = mid

    #最後にtargetとlowerが一致しているか判定
    if arry[lower] == target:
        return(lower)
    else:
        return(None)

次に検索値が重複する時に、検索値と同じ値の場所をリストで返すように拡張します。

import numpy as np

#適当なarrayを作成する
arry = [1,2,1,2,5,3,4,3,6,7,2,8,9,7,10]
arry = np.sort(arry)

#探索したい値を指定
target = 7

#二分探索
result = binary_search(arry, target)

#重複要素の検索
result_list = Duplication_search(result,arry)
#[10,11]

#---------------------------------
#2分探索
def binary_search(array, target):
    lower = 0                               
    upper = len(array) -1

    while lower < upper:#上限と下限が反転するまで探索
        mid = (lower + upper) // 2
        result = array[mid] #真ん中の要素を調べる

        if array[mid] < target:#小さければ下限を変更
            lower = mid + 1 
        else:#その他はここ
            upper = mid

    if array[lower] == target:#最後にtargetとlowerが一致しているか判定
        return(lower)
    else:
        return(None)

#------------------------------------
#重複要素の検索
def Duplication_search(result,arry):
    #Noneなら何もしない 要素があれば次の要素を検索する
    if result is None:
        pass
    else:
        result_list = []        
        #探索した要素があればさらに重複要素がないか調べていく
        while target == arry[result]:
            result_list.append(result)
            result = result + 1
        return(result_list)

重複要素は検索位置を後ろにずらして探索するようにしました。

次に検索値がリストで複数与えられた時のためにリストと値を判別するところを作成しました。

import numpy as np

#適当なarrayを作成する
arry = [1,2,1,2,5,3,4,3,6,7,2,8,9,7,10]
arry = np.sort(arry)

#探索したい値を指定
target = list(range(1,10,2))

#二分探索
result_list = Duplication_binary_search(arry, target)
result_list
#[0, 1, 5, 6, 8, 10, 11, 13]

#-----------------------------------------------------
#重複のある時の二分探索
def Duplication_binary_search(arry, target):
    result_list = []  
    #targetがリストで与えられた時
    if isinstance(target, list) == True:
        for item in target:
            result = binary_search(arry, item)
            result_list = Duplication_search(result,arry,item,result_list)
    #targetが単品の時
    else:
        result = binary_search(arry, target)
        result_list = Duplication_search(result,arry,target,result_list)  
    return(result_list)


#二分探索
def binary_search(arry,target):
    lower = 0                               
    upper = len(arry) -1

    while lower < upper:#上限と下限が反転するまで探索
        mid = (lower + upper) // 2
        result = arry[mid]
        if arry[mid] < target:#小さければ下限を変更
            lower = mid + 1 
        else:#その他はここ
            upper = mid

    #最後にtargetとlowerが一致しているか判定
    if arry[lower] == target:
        return(lower)
    else:
        return(None)


#重複要素検索用            
def Duplication_search(result,arry,target,result_list):
    #Noneなら何もしない 要素があれば次の要素を検索する
    if result is None:
        pass
    else:
        #探索した要素があればさらに重複要素がないか調べていく

        while target == arry[result]:
            result_list.append(result)
            result = result + 1
        return(result_list)

以上です。
プログラムを最近始めたばかりでコードを書くのが遅いので、なるべく汎用的なプログラムを作成し、使い回したいと思って作成しました。

一応動作確認をしているのでちゃんと動くと思っています。
でも、もっと分かりやすく短くまとめられると思います。

これからもっと勉強して分かりやすいコードをかけるようになったら、
また書き直したいと思います。