二分探索でソート済み配列から値を探す

二分探索問題 30

小さい順に並んだ整数から目当ての数の位置を探し、無ければ -1 を返す。探す範囲を毎回半分に狭める二分探索の練習です。

海外で定番の問題リスト 4 本のうち 2 本に入っています (NeetCode 150、Grind 75)

問題

小さい順に並んだ整数の並び nums と、整数 target を受け取ります。nums の中に target があれば、その位置 (0 から数えた番号) を返し、無ければ -1 を返す関数を書いてください。

nums の値は小さい順に並び、同じ値は 2 回出てきません
nums の長さは 0 以上 10000 以下、値はどれも -10000 以上 10000 以下です
時間は O(log n) で解いてください

入力と出力の例

例 1

nums = [-6, 0, 3, 8, 15, 21] target = 8

例 2

並びに無い数を探すと -1 です。

nums = [2, 5, 9, 13] target = 6

-1

例 3

端の数も見つけられます。

nums = [1, 4, 10] target = 10

面接での聞かれ方

面接では、問題文がもっと短く渡されることが多いです。

「ソート済みの配列から、目標の数のインデックスを返してください。無ければ -1 です」
書き終えたあとに「なぜ O(log n) になるのですか？」と続けて聞かれます
「同じ値が何個もあったら、どの位置を返しますか？」と、問題文に無い場合を聞かれることもあります

二分探索は短いコードですが、端の扱いで間違えやすい問題です。探す範囲を「両端を含む」と決めたことを先に言っておくと、そのあとの説明がぶれません。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「ソートと二分探索」に、この型の要点を表とコードでまとめています。

二分探索は、並んだデータの範囲を半分ずつ絞ります。100 万件でも 20 回ほどで 1 件になります。

まず考える手順

段 1

まずは素直に、前から 1 つずつ見ていく書き方を考えます。target と同じ数に出会えばその位置を返し、最後まで無ければ -1 を返します。正しく動きますが、時間は O(n) で、小さい順に並んでいることを使っていません。

段 2

並びが小さい順なら、真ん中の数を 1 つ見るだけで、半分を捨てられます。真ん中の数が target より小さければ、答えは右の半分にしかありません。大きければ左の半分にしかありません。

段 3

探す範囲を left と right の 2 つの位置で持ち、両端を含むと決めます。真ん中が小さければ left を真ん中の 1 つ右へ、大きければ right を真ん中の 1 つ左へ動かします。範囲に数が 1 つでも残っている間、つまり left <= right の間だけ繰り返し、範囲が空になったら -1 を返します。

解答

Python

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        both = left + right
        mid = both // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

JavaScript

function binarySearch(
  nums, target
) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(
      (left + right) / 2
    );
    if (nums[mid] === target) {
      return mid;
    }
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Go

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

nums が空のときは right が -1 から始まるので、繰り返しに入らずに -1 を返します。JavaScript の割り算は小数になるので、Math.floor で切り捨てて位置にします。Go は整数どうしの割り算が小数を切り捨てるので、/ のままで位置になります。

計算量

時間は O(log n) です。1 回見るたびに範囲がおよそ半分になるので、10000 個でも 14 回ほどで終わります
使う記憶は O(1) です。持つのは left、right、mid の 3 つの数だけです
段 1 の前から見る書き方は、時間が O(n) です。並びが小さい順という手がかりを使うと、ここまで縮みます

よくある間違い

止まる条件を left < right にする。 範囲に数が 1 つだけ残ったときに見ずに抜けてしまい、例 3 の 10 のような端の数を見落とします
left = mid や right = mid にする。 真ん中はもう見終わっているので、1 つずらさないと範囲が縮まない場合があり、繰り返しが止まらなくなります
真ん中の求め方で桁があふれる。 Python と JavaScript では起きにくいですが、整数の大きさに上限がある言語では、left と right を足した時点であふれることがあります。その言語では「left に、2 つの差の半分を足す」書き方にします

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.2確認日 2026年10月24日

def binary_search(nums: list[int], target: int) -> int: """ Goal: 何を返すか idea1: まず思いつく案 -> runtime: O(?) space: O(?) idea2: もっと速い案 -> runtime: O(?) space: O(?) edge case: 空、1 つだけ、など """ # ここに書きます pass # 「実行」を押すと、この行の結果が出ます print(binary_search([-6, 0, 3, 8, 15, 21], 8))