質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

タイムアウト

タイムアウトはイベント発生から完了までに掛かる経過時間に対する一定の待ち時間を指します。また、特定の時間が経過された場合に発生するイベントを指すこともあります。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

2回答

2444閲覧

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

nekowakaritu

総合スコア1

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

タイムアウト

タイムアウトはイベント発生から完了までに掛かる経過時間に対する一定の待ち時間を指します。また、特定の時間が経過された場合に発生するイベントを指すこともあります。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2020/05/30 02:23

質問内容

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()

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

括弧が抜けてますね笑

diff

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

投稿2020/05/30 02:49

nico25

総合スコア830

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

nekowakaritu

2020/05/30 03:12

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

2020/05/30 03:25 編集

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

2020/05/30 14:26

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

2020/06/09 13:59

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

0

python

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

投稿2020/05/30 02:47

yuki23

総合スコア1448

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

nekowakaritu

2020/05/30 03:12

ありがとうございます!!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問