二分探索を学び直す

はじめに

基本的な探索アルゴリズムの1つである、二分探索についてまとめる。

二分探索とは

二分探索とは、ソートされた状態の配列から目的のデータを高速に検索するアルゴリズムである。

探索範囲の中央値とターゲットを比較し、毎回探索範囲を半分に絞り込むことで、効率的に検索する。

計算量は、O(logN)である。

二分探索の流れ

1. 探索範囲の中央の値を確認する
2. 中央の値とターゲットを比較する
3. 一致すれば探索終了
4. ターゲットの方が大きければ右側を探索する
5. ターゲットの方が小さければ左側を探索する

具体例

実装

package binarysearch
 
func Search(arr []int, target int) int {
	left := 0
 
	right := len(arr) - 1
	for left <= right {
		mid := (left + right) / 2
		if arr[mid] == target {
			return mid
		}
		if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

• 参考実装Repository: https://github.com/yamaken87/sampler/tree/main/binarysearch

最後に

AI時代にアルゴリズムを再度学び直して、思い出そうと思いブログに残していく。

今後は、ツリー構造等も進めていきたい。