二分探索Python：ステップバイステップガイド

Pythonバイナリ検索では、並べ替えられた配列内のアイテムの位置が検出されます。リストを半分に分割します。指定された値が中央の数値よりも大きい場合、検索はリストの右側に焦点を合わせます。それ以外の場合、検索ではリストの左側にある番号が検索されます。

リスト内のアイテムの位置をどのように見つけますか？二分探索はそれに背を向けます。二分探索を使用すると、並べ替えられた配列内の要素の位置を簡単に見つけることができます。

コンピューターは、リストを検索して特定のアイテムを見つけるのが得意です。コンピューターがリスト内のアイテムを検索するために使用するルールは、検索アルゴリズムと呼ばれます。最も人気のあるPythonアルゴリズムの1つは、二分探索です。

このガイドでは、バイナリ検索とは何か、およびそれらがどのように機能するかについて説明します。 Pythonでのバイナリ検索の例を見ていき、プログラムにバイナリ検索を書き込む方法を学習できるようにします。始めましょう！

Pythonバイナリ検索とは何ですか？

Pythonバイナリ検索は、順序付けられた配列内の要素の位置を見つけるアルゴリズムです。二分探索は、リストを繰り返し2つに分割します。次に、検索により、値がリストの中央の値よりも高いか低いかが比較されます。

二分探索を実行する方法は2つあります。どちらのアプローチも、配列内の特定のポイントで最高位置と最低位置を追跡するために使用されるポインターを設定します。

使用できる最初のアプローチは、反復法です。このアプローチでは、一連のステートメントを繰り返して、配列内の要素の位置を決定します。 Pythonでは、 while この目的のためにループします。

もう1つのアプローチは、再帰的な方法です。これは、リスト内の要素が見つかるまで何度も自分自身を呼び出す関数を作成する場所です。再帰的方法では、前に説明した分割統治法を使用し、要素が見つかるまで検索プロセスを繰り返します。

参加者の81％は、ブートキャンプに参加した後、自分たちの技術的な仕事の見通しについてより自信を持っていると述べました。今日のブートキャンプにマッチしましょう。

平均的なブートキャンプの卒業生は、ブートキャンプの開始から最初の仕事を見つけるまで、キャリアの移行に6か月も費やしませんでした。

二分探索木Python：ステップバイステップ

分割統治と再帰についてのすべての話で、二分探索がどのように機能するかを正確に見失うことは簡単です。そのため、二分探索がどのように機能するかの例に直接飛び込みます。次のリストを検討してください：

7

9

14

22

34

リストから「22」という数字を検索します。

まず、リストに2つのポインターを設定します。 1つのポインターはリストの最大値を反映し、もう1つのポインターは最小値を反映します：

低				高
7	9	14	22	34

次のステップは、配列の中央の要素である14を見つけることです。この値が検索対象の値と等しい場合は、この値を返す必要があります。

この場合、14は22と同じではありません。したがって、プログラムで比較を実行する必要があります。

検索対象の番号を、現在の中央要素の右側にある要素の中央要素と比較します。これを行うのは、検索している番号が中央の番号よりも大きい場合のみです。それ以外の場合は、要素を現在の中央要素の左側にある中央要素と比較します。

数値22は14より大きいです。プログラムは22を現在の中央要素（14）の右側にある中央要素と比較し始めます。この場合、その数は22です。これは、検索対象の数と同じです。

		低	中	高
7	9	14	22	34

中間の価値を見つけました。プログラムは、その番号のインデックス位置を返します。この場合、22のインデックス位置は3です（リストは0からインデックス付けされることに注意してください）。

Pythonで二分探索を実装する方法

Pythonコードで手を汚しましょう。前に説明した両方のアプローチ、つまり反復メソッドと再帰メソッドを使用して、バイナリ検索のPython実装を調査します。

Pythonでの反復二分探索

反復法から始めましょう。ここで、リスト内のすべてのアイテムをループします。次に、リストの中央の値を見つけます。探している価値が見つかるまで、これを続けていきます。

二分探索関数

バイナリ検索用のPython関数を定義することから始めましょう：

def findValue(numbers, number_to_find):
	low = 0
	high = len(listnumbers - 1

	while low <= high:
		middle = low + (high - low) // 2

		if numbers[middle] == number_to_find:
			return middle
		elif numbers[middle] < number_to_find:
			low = middle + 1
		else:
			high = middle - 1
	return -1

この関数は、検索するリストと、リストで検索する数の2つのパラメーターを受け入れます。

次に、リストの最小値と最大値のデフォルト値を格納する2つのPython変数を宣言しました。 低 リストの開始インデックス値である0に設定されます。 高い リストの長さから1を引いた値に設定されます（リストはゼロからインデックス付けされるため）。

次のステップは、Pythonのwhileループを宣言することでした。このループは、最小の要素が最大の数値以下のときに実行されます。これは、番号がまだ見つからない場合にのみループが実行されることを意味します。

次に、中間の数値を計算します。これを行うには、最大値から最小値を減算します。次に、2で割ったときのその数値のモジュロ（余り）を計算します。次に、モジュロを最小の数値の値に加算します。

リストの真ん中の番号が検索したい番号と同じである場合、その番号の位置を返します。

新しい「低い」数値を中央の位置より1大きい値に設定します。これは、真ん中の数が検索したい数よりも少ない場合に発生します。これにより、前の視覚的な例で行ったように、検索がリストの左側に移動します。

それ以外の場合は、「高」の数値を中央の位置より1小さい値に設定します。これにより、検索がリストの右側に移動します。

これは、lowがhigh以下になるまで繰り返されます。値が見つからない場合は、-1を返します。その理由については後ほど説明します。

検索を実行する

プログラムの下部、 findValueの外に次のコードを追加します 機能：

numbers = [7, 9, 14, 22, 34]
number_to_find = 22

final = findValue(numbers, number_to_find)

if final == -1:
	print("This item was not found in the list.")
else:
	print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

まず、検索するアイテムのリストを宣言します。次に、検索する番号である22を指定しました。

次に、 findValue（）を呼び出します。 関数を作成し、リストを渡します。

ここで、以前から-1が入ります。関数によって返される数が-1の場合、それはアイテムがリストに見つからなかったことを意味します。検索関数は負の数を返すことができないため、プログラマーはこのような状況で-1を使用することがよくあります。

それ以外の場合、プログラムはその値のインデックス位置を通知するメッセージを出力します。

コードは次のようになります：

The number 22 was found at index position 3.

これで、22という数字がインデックス位置3に表示されることがわかりました。

Pythonでの再帰的二分探索

再帰を使用して二分探索を実行することもできます。ここで、条件（番号が見つかった）が満たされるまで自分自身を呼び出し続ける関数を定義します。

再帰関数を定義する

最後の例のように、まず、二分探索を実行する関数を記述します。

def findValue(numbers, number_to_find, low, high):
	if high >= low:
		middle = low + (high - low) // 2

		if numbers[middle] == number_to_find:
			return middle
		elif numbers[middle] < number_to_find:
			return findValue(numbers, number_to_find, middle + 1, high)
		else:
			return findValue(numbers, number_to_find, low, middle - 1)
	
	else:
		return -1

私たちのコードは、前の例と多少似ています。

まず、最高値が最低値以上であるかどうかを確認します。そうである場合、プログラムは-1を返します。それ以外の場合は、バイナリ検索の実行を開始します。

最後の例と同じアプローチを使用して、中間数を計算します。まず、最高値から最低値を引きます。次に、2で割ったときのその値のモジュロ（余り）を計算します。最後に、最小の数値を加算します。

次に、 if 二分探索をどのように進めるかを決定するステートメント：

• 真ん中の数字が探している数字と等しい場合、その数字の位置が返されます。
• 中間の数値が探している数値よりも小さい場合は、 findValue（） 関数が再度呼び出されます。今回は、 lowの値 中間値より1大きい値に設定されます。
• 中央の数値が探している数値よりも大きい場合、 findValue（） 関数が呼び出されます。 「高」の値は、中央の値より1小さい値になります。

メインプログラムを書く

あとはメインプログラムを書くだけです：

numbers = [7, 9, 14, 22, 34]
number_to_find = 22

final = findValue(numbers, number_to_find, 0, len(numbers) - 1)

if final == -1:
	print("This item was not found in the list.")
else:
	print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

私たちのメインプログラムは、前の例と同じですが、1つ違いがあります。 findValue（）に2つの新しいパラメータを渡します。 機能：低と高。

アルゴリズムは再帰的であり、関数でこれらの値を割り当てることができないため、これを行う必要があります。関数に値を割り当てた場合、関数が実行されるたびにそれらの値がリセットされ、検索アルゴリズムが機能しなくなります。

コードは次のようになります：

The number 22 was found at index position 3.

以前と同じ結果を受け取りました。この例では、反復プログラムの代わりに再帰プログラムを使用して、バイナリ検索を実行しました。

Pythonバイナリ検索をいつ使用する必要がありますか？

二分探索は、数値のリストを検索する効率的な方法です。この検索は、線形検索よりも効率的です。これは、バイナリ方式では、並べ替えられたリストの中央が見つかるとすぐに検索が半分に削減されるためです。

バイナリ検索を使用してリストを検索する前に、リストを番号順に並べ替える必要があることに注意してください。二分探索を実行する前に、番号が昇順でソートされていることを確認してください。

Pythonの複雑さの内訳での二分探索

二分探索の複雑さは何ですか？それは良い質問です。

二分探索アルゴリズムのベストケースの複雑さはO（1）です。これは、最初の比較が検索対象のアイテムと等しい場合に発生します。

二分探索の平均および最悪の場合の複雑さはO（log n）です。これは、リスト内で検索するアイテムの数に応じて、検索の実行にかかる時間が対数的に増加することを意味します。

結論

バイナリ検索は、リスト内の値のインデックス位置を見つけるための効率的な方法です。

バイナリ検索が実行されるたびに、検索はリストを2つの部分に分割します。検索は、検索している番号に最も近いリストの側に焦点を合わせます。

検索が実行されるたびに、プログラムが検索する必要のある数値の量は半分になります。

Pythonの詳細については、Pythonの学習方法ガイドをご覧ください。