検索ガイド -Search Guide-

単語と単語を空白で区切ることで AND 検索になります。
例: python デコレータ ('python' と 'デコレータ' 両方を含む記事を検索します)
単語の前に '-' を付けることで NOT 検索になります。
例: python -デコレータ ('python' は含むが 'デコレータ' は含まない記事を検索します)
" (ダブルクオート) で語句を囲むことで 完全一致検索になります。
例: "python data" 実装 ('python data' と '実装' 両方を含む記事を検索します。'python data 実装' の検索とは異なります。)
python_coding_challenge

Python coding challenge - 変化球バイナリサーチアルゴリズム (binary search algorithm) を ループ処理 / 再帰処理 の2通りで実装してみよう! 投稿一覧へ戻る

Published 2022年7月14日8:10 by mootaro23

SUPPORT UKRAINE

- Your indifference to the act of cruelty can thrive rogue nations like Russia -

Python Coding Challenge (binary search)
(Python コーディングチャレンジ [変化球バイナリサーチ編])

今回は binary search アルゴリズムの実装です。ちょっとググれば色々とヒットしますので、面白くするために少しだけ変化球を用意しました。
問題:
昇順にソート済みの int 値を要素とする list が与えられます。
検索する int 値 (target) が与えられたとき、list に含まれて入ればそのインデックス番号、含まれていなければ list の昇順ソートを保つように挿入すべきインデックス番号を返すバイナリサーチアルゴリズムを実装してください。
この時、target が list 中に存在したのか存在しなかったのかが後で判断できるように、target が list 中に存在した場合は (インデックス番号, True)、存在しなかった場合は (インデックス番号, False) という tuple を返さなければいけません。
課題 1:
while ループを利用して実装してください。関数定義は以下のような形です (同じである必要はありません):
def binary_search_loop(arr: list[int], target: int) -> tuple[int, bool]:
...
次のテストをパスする必要があります:
import unittest

class TestBinarySearchLoop(unittest.TestCase):

def setUp(self):
self.arr = [1, 3, 5, 6, 9]

def test_target_1_index_0(self):
res = binary_search_loop(self.arr, 1)
self.assertEqual((0, True), res, f'Result: {res} expected (0, True)')

def test_target_5_index_2(self):
res = binary_search_loop(self.arr, 5)
self.assertEqual((2, True), res, f'Result: {res} expected (2, True)')

def test_target_9_index_4(self):
res = binary_search_loop(self.arr, 9)
self.assertEqual((4, True), res, f'Result: {res} expected (4, True)')

def test_target_minus_3_index_0(self):
res = binary_search_loop(self.arr, -3)
self.assertEqual((0, False), res, f'Result: {res} expected (0, False)')

def test_target_0_index_0(self):
res = binary_search_loop(self.arr, 0)
self.assertEqual((0, False), res, f'Result: {res} expected (0, False)')

def test_target_2_index_1(self):
res = binary_search_loop(self.arr, 2)
self.assertEqual((1, False), res, f'Result: {res} expected (1, False)')

def test_target_7_index_4(self):
res = binary_search_loop(self.arr, 7)
self.assertEqual((4, False), res, f'Result: {res} expected (4, False)')

def test_target_10_index_5(self):
res = binary_search_loop(self.arr, 10)
self.assertEqual((5, False), res, f'Result: {res} expected (5, False)')
課題 2:
再帰関数 (recursive function) として実装してください。関数定義は以下のような形です (同じである必要はありません):
def binary_search_recursive(arr: list[int], start_index: int, last_index: int, target: int) -> tuple[int, bool]:
...
次のテストをパスする必要があります:
import unittest

class TestBinarySearchRecursive(unittest.TestCase):

def setUp(self):
self.arr = [1, 3, 5, 6, 9]

def test_target_1_index_0(self):
res = binary_search_recursive(self.arr, 0, len(self.arr) - 1, 1)
self.assertEqual((0, True), res, f'Result: {res} expected (0, True)')

def test_target_5_index_2(self):
res = binary_search_recursive(self.arr, 0, len(self.arr) - 1, 5)
self.assertEqual((2, True), res, f'Result: {res} expected (2, True)')

def test_target_9_index_4(self):
res = binary_search_recursive(self.arr, 0, len(self.arr) - 1, 9)
self.assertEqual((4, True), res, f'Result: {res} expected (4, True)')

def test_target_minus_3_index_0(self):
res = binary_search_recursive(self.arr, 0, len(self.arr) - 1, -3)
self.assertEqual((0, False), res, f'Result: {res} expected (0, False)')

def test_target_0_index_0(self):
res = binary_search_recursive(self.arr, 0, len(self.arr) - 1, 0)
self.assertEqual((0, False), res, f'Result: {res} expected (0, False)')

def test_target_2_index_1(self):
res = binary_search_recursive(self.arr, 0, len(self.arr) - 1, 2)
self.assertEqual((1, False), res, f'Result: {res} expected (1, False)')

def test_target_7_index_4(self):
res = binary_search_recursive(self.arr, 0, len(self.arr) - 1, 7)
self.assertEqual((4, False), res, f'Result: {res} expected (4, False)')

def test_target_10_index_5(self):
res = binary_search_recursive(self.arr, 0, len(self.arr) - 1, 10)
self.assertEqual((5, False), res, f'Result: {res} expected (5, False)')
さて楽しんでいただけたでしょうか?
バイナリサーチ (binary search) は 1 回の検索処理毎に対象であるコレクションの範囲を 1/2 に狭めていくため、最悪計算時間は O(log n) と非常に高速です。ただし対象となるコレクションが「ソート済みである」ということが前提となります。
また、「バイナリサーチ (binary search)」と一言で言っても、ここで見たように実装方法は1つだけではありませんし、実装方法によって計算実行時間に違いが生じます。ここで見た2つの方法では、ループだけで処理する方が再帰動作で処理するよりも計算実行時間は速くなります。
以下に実装例を掲載します。参考にしつつ改良、変更を加えてみてください:
バイナリサーチアルゴリズム・ループ処理実装例:
def binary_search_loop(arr: list[int], target: int) -> tuple[int, bool]:
start_index = 0
last_index = len(arr)

while start_index < last_index:
mid_index = (last_index + start_index) // 2
if arr[mid_index] == target:
return (mid_index, True)

if arr[mid_index] < target:
start_index = mid_index + 1
else:
last_index = mid_index
return (start_index, False)
バイナリサーチアルゴリズム・再帰動作処理実装例:
def binary_search_recursive(arr: list[int], start_index: int, last_index: int, target: int) -> tuple[int, bool]:
if start_index > last_index:
return (start_index, False)

mid_index = (last_index + start_index) // 2
if arr[mid_index] == target:
return (mid_index, True)

if arr[mid_index] < target:
start_index = mid_index + 1
else:
last_index = mid_index - 1

return binary_search_recursive(arr, start_index, last_index, target)