【python】二分探索で速度の違いがでる書き方の違いがわからない。

Question

質問内容

AOJの二分探索の問題 - ALDS1_4_B

二分探索をして該当の数字がふくまれているのかを判定する問題です。
自分が書いたコードでは、テストデータで探索範囲となる数列が100000個になったときにタイムアウト判定となってしまいます。
正解するコードを見てみて、違いはあるものの自分の書いたコードのどの部分がボトルネックになっているのかが比べてもわからなかったので、教えていただきたいです。

該当のソースコード

時間制限でアウトになるコード

def binarySearch(aim, parent):
    left = 0
    right = len(parent)-1
    while left < right:
        center = right+left//2
        if parent[center] > aim:
            right = center-1
        elif parent[center] < aim:
            left = center
        elif parent[center] == aim:
            return True
    return False

def main():
    _ = input()
    array_A = list(map(int, input().split()))
    _ = input()
    array_B = list(map(int, input().split()))

    cnt = 0
    for integer_B in array_B:
        if binarySearch(integer_B, array_A):
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

正解になるコード

def binary_search(array, tgt_no): #  arrayは昇順にソートされているものとする

    def compare_midpoint(tgt, array, start, end):
        midpoint = (end + start)//2
        if tgt == array[midpoint]:
            return True, None, None
        elif tgt < array[midpoint]:
            return False, start, midpoint
        elif tgt > array[midpoint]:
            return False, midpoint + 1, end

    start = 0
    end = len(array)
    while True:
        ret, start, end = compare_midpoint(tgt_no, array, start, end)
        if ret:
            return True
        if end <= start:
            return False

def main():
    _ = input()
    array_A = list(map(int, input().split()))
    _ = input()
    array_B = list(map(int, input().split()))

    cnt = 0
    for integer_B in array_B:
        if binary_search(array_A, integer_B):
            cnt += 1

    print(cnt)
    return


main()

Answer 1

括弧が抜けてますね笑

-        center = right+left//2
+        center = (right+left)//2

• Python で二分探索

Comments

[nekowakaritu]

ありがとうございました！
カッコ完全にわすれていたんですが、それで提出してテストケース９まで正解していたのが、不可解ですが。。。
載せていただいたサイトも参考に書き直して、正解になりました。

[swordone]

勘違いコメントしました。

[nekowakaritu]

OKです

[ikadzuchi]

> テストケース９まで正解していたのが、不可解
「center = right+left//2」は(leftが0である限り)center=rightになり、
parent[center] == aimになるまでずっと「if parent[center] > aim:」の方を通って、
「right = center-1」で1づつ範囲が狭まっていくので、
無駄な全探索をしていますが正しい答えは出ますね。

[nekowakaritu]

なるほど！！
スッキリしました！ありがとうございます！

Answer 2

        center = right+left//2
```カッコで囲んでください

Comments

[nekowakaritu]

ありがとうございます！！