Binary Search

探索

ソート済みの配列から目的の値を効率よく見つけるアルゴリズム。先頭から順に見る線形探索と違い、「中央の値と比較して、探索範囲を半分に絞り込む」を繰り返す。

計算量

線形探索は最悪 O(n)。二分探索は毎回探索範囲を半分にできるため O(log n)。要素数が100万でも、たかだか20回の比較で見つかる(2^20 ≈ 100万)。

前提条件: 配列が昇順にソート済みであること。ソートされていない配列には使えない。

なぜ必要か

「探す」はプログラミングで最頻出の操作の一つで、線形探索のO(n)が効いてくる規模になった瞬間に体感速度が変わる。さらに蟻本では、二分探索の本質は「配列から値を探す」だけでなく「単調な条件を満たす境界を見つける」ことだと強調される(通称めぐる式二分探索)。たとえば「ある値以上に初めてなるインデックス」のような、答えが単調に変化する問題全般に応用でき、DPの前処理や最適化問題の下ごしらえとしてもよく使われる基礎ツール。

具体例

配列 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] (index 0〜9) から 7 を探す:

lo=0, hi=9 → mid=4, s[4]=9。7 < 9 なので左半分へ(hi=3)
lo=0, hi=3 → mid=1, s[1]=3。7 > 3 なので右半分へ(lo=2)
lo=2, hi=3 → mid=2, s[2]=5。7 > 5 なので右半分へ(lo=3)
lo=3, hi=3 → mid=3, s[3]=7。一致、index=3を返す

flowchart TD
  A["lo=0, hi=n-1"] --> B{"lo <= hi?"}
  B -- No --> Z["見つからない: -1"]
  B -- Yes --> C["mid = lo + (hi-lo)/2"]
  C --> D{"s[mid] == target?"}
  D -- Yes --> E["mid を返す"]
  D -- No --> F{"s[mid] < target?"}
  F -- Yes --> G["lo = mid + 1"]
  F -- No --> H["hi = mid - 1"]
  G --> B
  H --> B

出典

『プログラミングコンテストチャレンジブック』(通称「蟻本」) 2-2節「探索」、杉浦・海野・矢吹『アルゴリズム図鑑』「二分探索」。

Java

まだJava版はありません。

mid := lo + (hi-lo)/2 で書くのが定石((lo+hi)/2 だと lo, hi が非常に大きいとき整数オーバーフローする可能性があるため避ける)。

実行: go run ./Algorithms/patterns/BinarySearch/go

$ go run ./Algorithms/patterns/BinarySearch/go

binarysearch.go

package main

// BinarySearch はソート済みスライス s から target のインデックスを二分探索で返す。
// 見つからなければ -1 を返す。
//
// 計算量: O(log n)。探索範囲を毎回半分に絞り込むため、
// 線形探索の O(n) に対して要素数が100万でも高々20回の比較で済む。
// 前提条件: s は昇順にソート済みであること。
func BinarySearch(s []int, target int) int {
	lo, hi := 0, len(s)-1
	for lo <= hi {
		mid := lo + (hi-lo)/2 // (lo+hi)/2 はオーバーフローの可能性があるので避ける定石
		switch {
		case s[mid] == target:
			return mid
		case s[mid] < target:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return -1
}

main.go

package main

import "fmt"

// 実行: go run ./Algorithms/patterns/BinarySearch/go
func main() {
	s := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
	for _, target := range []int{7, 4, 19, 1} {
		idx := BinarySearch(s, target)
		fmt.Printf("target=%2d -> index=%d\n", target, idx)
	}
}

PHP

まだPHP版はありません。

TypeScript

まだTypeScript版はありません。

Python

まだPython版はありません。