RSSフィードを購読
Python Coding Challenge (binary search)
(Python コーディングチャレンジ [変化球バイナリサーチ編])
(Python コーディングチャレンジ [変化球バイナリサーチ編])
今回は binary search アルゴリズムの実装です。ちょっとググれば色々とヒットしますので、面白くするために少しだけ変化球を用意しました。
問題：
昇順にソート済みの int 値を要素とする list が与えられます。
検索する int 値 (target) が与えられたとき、list に含まれて入ればそのインデックス番号、含まれていなければ list の昇順ソートを保つように挿入すべきインデックス番号を返すバイナリサーチアルゴリズムを実装してください。
この時、target が list 中に存在したのか存在しなかったのかが後で判断できるように、target が list 中に存在した場合は (インデックス番号, True)、存在しなかった場合は (インデックス番号, False) という tuple を返さなければいけません。
課題 １:
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)')
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)')
課題 ２:
再帰関数 (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)')
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)」と一言で言っても、ここで見たように実装方法は１つだけではありませんし、実装方法によって計算実行時間に違いが生じます。ここで見た２つの方法では、ループだけで処理する方が再帰動作で処理するよりも計算実行時間は速くなります。
以下に実装例を掲載します。参考にしつつ改良、変更を加えてみてください:
バイナリサーチアルゴリズム・ループ処理実装例:
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)
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)
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)