[Q&A] 二分探索のプログラムの出力結果が正しく出されないので間違いを指摘して頂きたい

二分探索のプログラムの出力結果が正しく出されないので間違いを指摘して頂きたい

解決したいこと

二分探索を行うプログラムをPythonで書きました。
しかし、エラーは無いものの、すべてのテストコードで探索失敗と表記されてしまいます。皆さんのお力添えで正しくprintされるように直すべき箇所を指摘して頂きたいです。宜しくお願い致します。

発生している問題・エラー

エラーメッセージはありません。

該当するソースコード

A = [2, 4, 6, 8, 10, 12, 14]
X = 6   /*探索値*/
L = 1  /*探索範囲の始点*/
H = 7  /*探索範囲の中間*/
M = (L + H) // 2  /*探索範囲の終点*/

while (L <= H) and (A[M - 1] != X): 
  if A[M - 1] <= X:  /*中間に位置する値との比較*/
    L = M + 1 /*次の探索を右方向へ*/
  else:
    H = M + 1 /*次の探索を左方向へ*/
    break
      
    M = (L + H) // 2

if L >= H:
  print("探索成功")
else:
  print("探索失敗")

自分で試したこと

listのindex範囲を変えてみました。

3Answer

@Mt_SQ posted at 2024-03-08

このままでは、１回めのifで「偽」となり、whileループを脱してしまいます。
結果として「探索失敗」になります。

初学者の方のようなので、まずは、紙と鉛筆を使って手作業でトレースしてみることをおすすめします。

ループ内や分岐時に、変数をprint出力するだけでも誤りを見つけやすくなります。

とりあえずはprintを挿入し、インデントを修正して実行したものを添えます。
少しは問題点が見えてくるかと思います。

Python 3.11.2 (main, Mar 13 2023, 12:18:29) [GCC 12.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> A = [2, 4, 6, 8, 10, 12, 14]
>>> X = 6  # 探索値
>>> L = 1  # 探索範囲の始点
>>> H = 7  # 探索範囲の終点
>>> M = (L + H) // 2  # 探索範囲の中間
>>> 
>>> while (L <= H) and (A[M - 1] != X):
...     print('判断前\t', '\tL=', L, '\tH=', H, '\tM=', M)
...     if A[M - 1] <= X:  # 中間に位置する値との比較
...         L = M + 1  # 次の探索を右方向へ
...         print('真 処理後', '\tL=', L, '\tH=', H, '\tM=', M)
...     else:
...         H = M + 1  # 次の探索を左方向へ
...         print('偽 処理後', '\tL=', L, '\tH=', H, '\tM=', M)
...         break
...     M = (L + H) // 2  # インデントを修正
... 
判断前          L= 1    H= 7    M= 4
偽 処理後       L= 1    H= 5    M= 4
>>> if L >= H:
...     print('探索成功')
... else:
...     print('探索失敗')
... 
探索失敗
>>>

他、問題に直接関係ない点で、いくつか気になったところです。

listのindexが0から始まることを意識して書いてみてはどうでしょう。L = 1 , H = 7と書きたい気持ちは理解できますが。
break後のM = (L + H) // 2のインデント位置は誤りです。
４行目と５行目のコメントが逆です。
Pythonのコメントは#です。

ご自身で解決していただきたく、最小限の指摘にとどめさせていただきました。

1Like

@nak435 posted at 2024-03-08

二分探索ですから、毎回シンプルに”二分”しないと・・・

A = [2, 4, 6, 8, 10, 12, 14]
X = 6       #探索値
L = 0       #探索範囲の始点
H = len(A)  #探索範囲の終点

while (H - L) > 1:
  M = (L + H) // 2  #探索範囲の中間
  if A[M] <= X:     #中間に位置する値との比較
    L = M   #次の探索を左半分へ
  else:
    H = M   #次の探索を右半分へ

if A[L] == X:
  print(X, "探索成功")
else:
  print(X, "探索失敗")

変数 L、H をトレースすると、二分する様子が分かると思います。

1Like

@jinbei230525 posted at 2024-03-07

0Like

Are you sure you want to delete the question?