1204_Pythonでバイナリーサーチのスクリプト

Q.1

pythonでバイナリーサーチのスクリプトを作成して下さい。

A.1

略。

以下は誤り。

# リストを定義する
my_list = [1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 8, 8, 8]

# 結果を格納するリストを作成する
result = []

# リストの最初と最後のインデックスを取得する
low = 0
high = len(my_list) - 1

# リストの最初と最後の要素を結果に追加する
result.append(low)
result.append(high)

# バイナリーサーチを応用する関数を定義する
def binary_search_modified(list, low, high):
  # リストの範囲がなくなるまで繰り返す
  while low <= high:
    # リストの中央のインデックスを計算する
    mid = (low + high) // 2
    # 中央の要素を取得する
    guess = list[mid]
    # 前の要素を取得する
    prev = list[mid - 1]
    # 中央の要素と前の要素を比較する
    if guess > prev:
      # 要素の数字がひとつ増えたら、インデックスを結果に追加する
      result.append(mid)
      # リストの右半分を調べる
      low = mid + 1
    else:
      # 要素の数字が同じなら、リストの左半分を調べる
      high = mid - 1

# バイナリーサーチを応用する関数を呼び出す
binary_search_modified(my_list, low, high)

# 結果をソートする
result.sort()

# 結果を表示する
print(result) # [0, 3, 5, 9, 11, 14, 16, 17, 19]

正解は以下。

# リストを定義する
my_list = [1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 8, 8, 8]

# 結果を格納するリストを作成する
result = []

# リストの最初と最後のインデックスを取得する
low = 0
high = len(my_list) - 1

# リストの最初の要素を結果に追加する
result.append(low)

# バイナリーサーチを応用する関数を定義する
def binary_search_modified(list, low, high):
  # リストの範囲がなくなるまで繰り返す
  while low <= high:
    # リストの中央のインデックスを計算する
    mid = (low + high) // 2
    # 中央の要素を取得する
    guess = list[mid]
    # 前の要素を取得する
    prev = list[mid - 1]
    # 中央の要素と前の要素を比較する
    if guess > prev:
      # 要素の数字がひとつ増えたら、インデックスを結果に追加する
      result.append(mid)
      # リストの右半分を調べる
      low = mid + 1
    else:
      # 要素の数字が同じなら、リストの左半分を調べる
      high = mid - 1

# バイナリーサーチを応用する関数を呼び出す
binary_search_modified(my_list, low, high)

# リストの最後の要素の前の要素と比較する
if my_list[-1] > my_list[-2]:
  # 要素の数字がひとつ増えたら、インデックスを結果に追加する
  result.append(len(my_list) - 1)

# 結果をソートする
result.sort()

# 結果を表示する
print(result) # [0, 3, 5, 9, 11, 14, 16, 17]