質問内容
二分探索をして該当の数字がふくまれているのかを判定する問題です。
自分が書いたコードでは、テストデータで探索範囲となる数列が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()
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2020/05/30 03:12
2020/05/30 03:25 編集
2020/05/30 03:26
2020/05/30 14:26
2020/06/09 13:59