小さい順の並びから位置を探す｜コーディング面接問題

問題

小さい順に並んだ整数の並び 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) になるのですか？」と続けて聞かれます
「同じ値が何個もあったら、どの位置を返しますか？」と、問題文に無い場合を聞かれることもあります

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

まず考える手順

段 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;
}

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

計算量

時間は 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 つの差の半分を足す」書き方にします

面接での話し方の例

書き始める前に、方針を短く口に出します。

「並びが小さい順なので、真ん中の数と比べれば半分を捨てられます。範囲は両端を含む形で持ち、範囲に数が残っている間だけ繰り返します。時間は O(log n)、記憶は O(1) です。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 2 の [2, 5, 9, 13] で 6 を探します。最初の真ん中は 5 で、6 より小さいので左の端を 9 の位置へ動かします。次の真ん中は 9 で、6 より大きいので右の端を 5 の位置へ戻します。ここで左の端が右の端を越えたので、範囲が空になり -1 を返します。」

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