Zenn
🤖

二分探索 (Binary Search)をGoで実装してみた

2024/12/12に公開
Go
アルゴリズム
tech

はじめに

二分探索 (Binary Search) は、整列された配列やリストから特定の要素を効率的に探し出すためのアルゴリズムです。検索範囲を毎回半分に絞り込むことで、非常に高速に検索を行うことができます。

  • 時間計算量: O(log n)
  • 適用条件: データが昇順または降順に整列されていること

この記事では、Goでの二分探索の実装と、二分探索と線形探索のパフォーマンス比較を行います。

二分探索とは？

二分探索法は以下の手順で動作します。

  1. 中央の要素を取得
  2. 目的値との比較
    • 一致する場合：検索終了
    • 一致しない場合：目的値が中央の要素より小さいか大きいかを判定
  3. 配列を中央の要素を基準に2つに分割し、探索範囲を狭める
  4. 上記の手順を、範囲が1つの要素になるまで繰り返す

なぜ二分探索は整列されたデータが必要なのか？

二分探索は、配列の中央の要素を基準に「目的値が左側にあるか」「右側にあるか」を判断することで、効率的に探索範囲を絞り込みます。この判断が正しく行われるためには、データが昇順または降順に整列されている必要があります。
例えば、昇順の場合は以下のように判断できます。

  • 目的値が中央の要素より小さい：目的値は左側の範囲に存在する
  • 目的値が中央の要素より大きい：目的値は右側の範囲に存在する

整列されていないデータでは、この比較が成り立たないため、探索範囲を適切に絞り込むことができません。

実装例

以下は、昇順の配列に対してGo言語で実装した二分探索のコードです。

package algorithm

import "cmp"

func BinarySearch[T cmp.Ordered](arr []T, target T) int {
	left, right := 0, len(arr)-1
	for left <= right {
		mid := left + (right-left)/2
		if arr[mid] == target {
			return mid
		} else if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

テストコード

次に、二分探索が正しく動作するかを検証するためのテストコードです。ランダムに生成したソート済み配列に対して検索を行い、結果が正しいことを確認します。

func TestBinarySearch(t *testing.T) {
	const L = 100
	for i := 0; i < 100; i++ {
		arr := make([]int, L)
		for j := 0; j < L; j++ {
			arr[j] = rand.IntN(L)
		}
		sort.Ints(arr)

		target := rand.IntN(L)
		index := BinarySearch[int](arr, target)

		if index >= 0 {
			if arr[index] != target {
				t.Fail()
			}
		} else {
			for _, ele := range arr {
				if ele == target {
					t.Fail()
				}
			}
		}
	}
}

二分探索と線形探索のベンチマーク比較

二分探索 (Binary Search) と 線形探索 (Linear Search) の実行速度を計測し、その結果を比較します。二つの探索アルゴリズムのパフォーマンスを測定し、どちらがより効率的であるかを実際のベンチマークデータを使って検証します。

ベンチマークコード

以下のコードは、BenchmarkBinarySearch と BenchmarkLinearSearch の2つのベンチマークを実装しています。それぞれ、二分探索と線形探索を実行し、パフォーマンスを測定しています。

func BenchmarkBinarySearch(b *testing.B) {
	const L = 1000
	arr := make([]int, L)
	for i := 0; i < L; i++ {
		arr[i] = i
	}
	sort.Ints(arr)

	target := rand.IntN(L)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		BinarySearch(arr, target)
	}
}

func BenchmarkLinearSearch(b *testing.B) {
	const L = 1000
	arr := make([]int, L)
	for i := 0; i < L; i++ {
		arr[i] = i
	}

	target := rand.IntN(L)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		LinearSearch(arr, target)
	}
}

比較結果

以下は、自分のPC上でのベンチマーク結果です。

探索アルゴリズム 実行回数 1回あたりの実行時間 メモリ使用量 アロケーション回数
二分探索 235,687,526回 4.338 ns/op 0 バイト 0 回
線形探索 23,342,997回 216.5 ns/op 0 バイト 0 回

この結果から、二分探索は線形探索よりもはるかに高速であることが確認できました。

二分探索の課題

二分探索 は非常に効率的なアルゴリズムですが、使用するにはいくつかの課題もあります。主な課題は、データが整列されていることが前提である点です。もしデータが整列されていない場合、二分探索を適用する前にソート処理が必要となります。この追加の処理が、場合によってはパフォーマンスに影響を与えることがあります。したがって、データの整列を最適化することが、二分探索の利点を最大限に引き出すための重要なポイントです。

Discussion