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]