コンテンツにスキップ

10.1   二分探索

二分探索（binary search）は、分割統治法に基づく効率的な探索アルゴリズムです。データが整列されていることを利用し、各反復で探索範囲を半分に縮め、目的の要素が見つかるか探索区間が空になるまで続けます。

問題

長さ \(n\) の配列 nums が与えられます。要素は昇順に並び、重複しません。要素 target を探し、そのインデックスを返してください。配列にその要素が含まれない場合は \(-1\) を返します。例を図 10-1 に示します。

二分探索の入力例二分探索の入力例

図 10-1   二分探索の入力例

図 10-2 のように、まずポインタ \(i = 0\) と \(j = n - 1\) を初期化し、配列の先頭要素と末尾要素をそれぞれ指すようにします。これらは探索区間 \([0, n - 1]\) を表します。角括弧は閉区間を表し、境界値そのものを含むことに注意してください。

続いて、次の二つの手順を繰り返します。

  1. 中点のインデックス \(m = \lfloor {(i + j) / 2} \rfloor\) を計算します。ここで \(\lfloor \: \rfloor\) は切り捨てを表します。
  2. nums[m] と target の大小関係を判定します。次の三つの場合があります。
    1. nums[m] < target なら、target は区間 \([m + 1, j]\) にあるため、\(i = m + 1\) とします。
    2. nums[m] > target なら、target は区間 \([i, m - 1]\) にあるため、\(j = m - 1\) とします。
    3. nums[m] = target なら、target が見つかったので、インデックス \(m\) を返します。

配列に目的の要素が含まれない場合、探索区間は最終的に空になります。このときは \(-1\) を返します。

二分探索の流れ二分探索の流れ

二分探索の手順 2二分探索の手順 2

二分探索の手順 3二分探索の手順 3

二分探索の手順 4二分探索の手順 4

二分探索の手順 5二分探索の手順 5

二分探索の手順 6二分探索の手順 6

二分探索の手順 7二分探索の手順 7

図 10-2   二分探索の流れ

\(i\) と \(j\) はともに int 型なので、\(i + j\) が int 型の値の範囲を超える可能性があることに注意してください。大きな値によるオーバーフローを避けるため、通常は \(m = \lfloor {i + (j - i) / 2} \rfloor\) という式で中点を計算します。

コードは次のとおりです。

binary_search.py
def binary_search(nums: list[int], target: int) -> int:
    """二分探索（閉区間）"""
    # 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    i, j = 0, len(nums) - 1
    # 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while i <= j:
        # 理論上、Python の数値は無限に大きくできる（メモリ容量による）ため、大きな数のオーバーフローを考慮する必要がない
        m = (i + j) // 2  # 中央のインデックス m を計算する
        if nums[m] < target:
            i = m + 1  # この場合、target は区間 [m+1, j] に存在する
        elif nums[m] > target:
            j = m - 1  # この場合、target は区間 [i, m-1] に存在する
        else:
            return m  # 目的の要素が見つかったので、そのインデックスを返す
    return -1  # 目的の要素が見つからなかったので、-1 を返す
binary_search.cpp
/* 二分探索（閉区間） */
int binarySearch(vector<int> &nums, int target) {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    int i = 0, j = nums.size() - 1;
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while (i <= j) {
        int m = i + (j - i) / 2; // 中央のインデックス m を計算する
        if (nums[m] < target)    // この場合、target は区間 [m+1, j] に存在する
            i = m + 1;
        else if (nums[m] > target) // この場合、target は区間 [i, m-1] に存在する
            j = m - 1;
        else // 目的の要素が見つかったので、そのインデックスを返す
            return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.java
/* 二分探索（閉区間） */
int binarySearch(int[] nums, int target) {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    int i = 0, j = nums.length - 1;
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while (i <= j) {
        int m = i + (j - i) / 2; // 中央のインデックス m を計算する
        if (nums[m] < target) // この場合、target は区間 [m+1, j] に存在する
            i = m + 1;
        else if (nums[m] > target) // この場合、target は区間 [i, m-1] に存在する
            j = m - 1;
        else // 目的の要素が見つかったので、そのインデックスを返す
            return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.cs
/* 二分探索（閉区間） */
int BinarySearch(int[] nums, int target) {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    int i = 0, j = nums.Length - 1;
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while (i <= j) {
        int m = i + (j - i) / 2;   // 中央のインデックス m を計算する
        if (nums[m] < target)      // この場合、target は区間 [m+1, j] に存在する
            i = m + 1;
        else if (nums[m] > target) // この場合、target は区間 [i, m-1] に存在する
            j = m - 1;
        else                       // 目的の要素が見つかったので、そのインデックスを返す
            return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.go
/* 二分探索（閉区間） */
func binarySearch(nums []int, target int) int {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    i, j := 0, len(nums)-1
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    for i <= j {
        m := i + (j-i)/2      // 中央のインデックス m を計算する
        if nums[m] < target { // この場合、target は区間 [m+1, j] に存在する
            i = m + 1
        } else if nums[m] > target { // この場合、target は区間 [i, m-1] に存在する
            j = m - 1
        } else { // 目的の要素が見つかったので、そのインデックスを返す
            return m
        }
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1
}
binary_search.swift
/* 二分探索（閉区間） */
func binarySearch(nums: [Int], target: Int) -> Int {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    var i = nums.startIndex
    var j = nums.endIndex - 1
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while i <= j {
        let m = i + (j - i) / 2 // 中央のインデックス m を計算する
        if nums[m] < target { // この場合、target は区間 [m+1, j] に存在する
            i = m + 1
        } else if nums[m] > target { // この場合、target は区間 [i, m-1] に存在する
            j = m - 1
        } else { // 目的の要素が見つかったので、そのインデックスを返す
            return m
        }
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1
}
binary_search.js
/* 二分探索（閉区間） */
function binarySearch(nums, target) {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    let i = 0,
        j = nums.length - 1;
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while (i <= j) {
        // 中央のインデックス m を計算し、parseInt() で小数点以下を切り捨てる
        const m = parseInt(i + (j - i) / 2);
        if (nums[m] < target)
            // この場合、target は区間 [m+1, j] に存在する
            i = m + 1;
        else if (nums[m] > target)
            // この場合、target は区間 [i, m-1] に存在する
            j = m - 1;
        else return m; // 目的の要素が見つかったので、そのインデックスを返す
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.ts
/* 二分探索（閉区間） */
function binarySearch(nums: number[], target: number): number {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    let i = 0,
        j = nums.length - 1;
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while (i <= j) {
        // 中央のインデックス m を計算する
        const m = Math.floor(i + (j - i) / 2);
        if (nums[m] < target) {
            // この場合、target は区間 [m+1, j] に存在する
            i = m + 1;
        } else if (nums[m] > target) {
            // この場合、target は区間 [i, m-1] に存在する
            j = m - 1;
        } else {
            // 目的の要素が見つかったので、そのインデックスを返す
            return m;
        }
    }
    return -1; // 目的の要素が見つからなかったので、-1 を返す
}
binary_search.dart
/* 二分探索（閉区間） */
int binarySearch(List<int> nums, int target) {
  // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
  int i = 0, j = nums.length - 1;
  // 探索区間が空になるまで繰り返す（i > j のとき空になる）
  while (i <= j) {
    int m = i + (j - i) ~/ 2; // 中央のインデックス m を計算する
    if (nums[m] < target) {
      // この場合、target は区間 [m+1, j] に存在する
      i = m + 1;
    } else if (nums[m] > target) {
      // この場合、target は区間 [i, m-1] に存在する
      j = m - 1;
    } else {
      // 目的の要素が見つかったので、そのインデックスを返す
      return m;
    }
  }
  // 目的の要素が見つからなかったので、-1 を返す
  return -1;
}
binary_search.rs
/* 二分探索（閉区間） */
fn binary_search(nums: &[i32], target: i32) -> i32 {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    let mut i = 0;
    let mut j = nums.len() as i32 - 1;
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while i <= j {
        let m = i + (j - i) / 2; // 中央のインデックス m を計算する
        if nums[m as usize] < target {
            // この場合、target は区間 [m+1, j] に存在する
            i = m + 1;
        } else if nums[m as usize] > target {
            // この場合、target は区間 [i, m-1] に存在する
            j = m - 1;
        } else {
            // 目的の要素が見つかったので、そのインデックスを返す
            return m;
        }
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.c
/* 二分探索（閉区間） */
int binarySearch(int *nums, int len, int target) {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    int i = 0, j = len - 1;
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while (i <= j) {
        int m = i + (j - i) / 2; // 中央のインデックス m を計算する
        if (nums[m] < target)    // この場合、target は区間 [m+1, j] に存在する
            i = m + 1;
        else if (nums[m] > target) // この場合、target は区間 [i, m-1] に存在する
            j = m - 1;
        else // 目的の要素が見つかったので、そのインデックスを返す
            return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.kt
/* 二分探索（閉区間） */
fun binarySearch(nums: IntArray, target: Int): Int {
    // 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
    var i = 0
    var j = nums.size - 1
    // 探索区間が空になるまで繰り返す（i > j のとき空になる）
    while (i <= j) {
        val m = i + (j - i) / 2 // 中央のインデックス m を計算する
        if (nums[m] < target) // この場合、target は区間 [m+1, j] に存在する
            i = m + 1
        else if (nums[m] > target) // この場合、target は区間 [i, m-1] に存在する
            j = m - 1
        else  // 目的の要素が見つかったので、そのインデックスを返す
            return m
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1
}
binary_search.rb
### 二分探索（閉区間） ###
def binary_search(nums, target)
  # 閉区間 [0, n-1] を初期化する。i, j は配列の先頭要素と末尾要素をそれぞれ指す
  i, j = 0, nums.length - 1

  # 探索区間が空になるまで繰り返す（i > j のとき空になる）
  while i <= j
    # 理論上、Ruby の数値は無限に大きくできる（メモリ容量による）ため、大きな数のオーバーフローを考慮する必要がない
    m = (i + j) / 2   # 中央のインデックス m を計算する

    if nums[m] < target
      i = m + 1 # この場合、target は区間 [m+1, j] に存在する
    elsif nums[m] > target
      j = m - 1 # この場合、target は区間 [i, m-1] に存在する
    else
      return m  # 目的の要素が見つかったので、そのインデックスを返す
    end
  end

  -1  # 目的の要素が見つからなかったので、-1 を返す
end
実行の可視化

時間計算量は \(O(\log n)\)：二分するループでは各反復で区間が半分になるため、反復回数は \(\log_2 n\) です。

空間計算量は \(O(1)\)：ポインタ \(i\) と \(j\) が使う領域は定数サイズです。

10.1.1   区間の表し方

前述の両端を含む閉区間のほか、「左閉右開」の区間もよく使われます。\([0, n)\) と表し、左端は含みますが右端は含みません。この表し方では、区間 \([i, j)\) は \(i = j\) のとき空になります。

この表し方でも、同じ機能を持つ二分探索を実装できます。

binary_search.py
def binary_search_lcro(nums: list[int], target: int) -> int:
    """二分探索（左閉右開区間）"""
    # 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    i, j = 0, len(nums)
    # 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while i < j:
        m = (i + j) // 2  # 中央のインデックス m を計算する
        if nums[m] < target:
            i = m + 1  # この場合、target は区間 [m+1, j) に存在する
        elif nums[m] > target:
            j = m  # この場合、target は区間 [i, m) に存在する
        else:
            return m  # 目的の要素が見つかったので、そのインデックスを返す
    return -1  # 目的の要素が見つからなかったので、-1 を返す
binary_search.cpp
/* 二分探索（左閉右開区間） */
int binarySearchLCRO(vector<int> &nums, int target) {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    int i = 0, j = nums.size();
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while (i < j) {
        int m = i + (j - i) / 2; // 中央のインデックス m を計算する
        if (nums[m] < target)    // この場合、target は区間 [m+1, j) に存在する
            i = m + 1;
        else if (nums[m] > target) // この場合、target は区間 [i, m) に存在する
            j = m;
        else // 目的の要素が見つかったので、そのインデックスを返す
            return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.java
/* 二分探索（左閉右開区間） */
int binarySearchLCRO(int[] nums, int target) {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    int i = 0, j = nums.length;
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while (i < j) {
        int m = i + (j - i) / 2; // 中央のインデックス m を計算する
        if (nums[m] < target) // この場合、target は区間 [m+1, j) に存在する
            i = m + 1;
        else if (nums[m] > target) // この場合、target は区間 [i, m) に存在する
            j = m;
        else // 目的の要素が見つかったので、そのインデックスを返す
            return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.cs
/* 二分探索（左閉右開区間） */
int BinarySearchLCRO(int[] nums, int target) {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    int i = 0, j = nums.Length;
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while (i < j) {
        int m = i + (j - i) / 2;   // 中央のインデックス m を計算する
        if (nums[m] < target)      // この場合、target は区間 [m+1, j) に存在する
            i = m + 1;
        else if (nums[m] > target) // この場合、target は区間 [i, m) に存在する
            j = m;
        else                       // 目的の要素が見つかったので、そのインデックスを返す
            return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.go
/* 二分探索（左閉右開区間） */
func binarySearchLCRO(nums []int, target int) int {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    i, j := 0, len(nums)
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    for i < j {
        m := i + (j-i)/2      // 中央のインデックス m を計算する
        if nums[m] < target { // この場合、target は区間 [m+1, j) に存在する
            i = m + 1
        } else if nums[m] > target { // この場合、target は区間 [i, m) に存在する
            j = m
        } else { // 目的の要素が見つかったので、そのインデックスを返す
            return m
        }
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1
}
binary_search.swift
/* 二分探索（左閉右開区間） */
func binarySearchLCRO(nums: [Int], target: Int) -> Int {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    var i = nums.startIndex
    var j = nums.endIndex
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while i < j {
        let m = i + (j - i) / 2 // 中央のインデックス m を計算する
        if nums[m] < target { // この場合、target は区間 [m+1, j) に存在する
            i = m + 1
        } else if nums[m] > target { // この場合、target は区間 [i, m) に存在する
            j = m
        } else { // 目的の要素が見つかったので、そのインデックスを返す
            return m
        }
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1
}
binary_search.js
/* 二分探索（左閉右開区間） */
function binarySearchLCRO(nums, target) {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    let i = 0,
        j = nums.length;
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while (i < j) {
        // 中央のインデックス m を計算し、parseInt() で小数点以下を切り捨てる
        const m = parseInt(i + (j - i) / 2);
        if (nums[m] < target)
            // この場合、target は区間 [m+1, j) に存在する
            i = m + 1;
        else if (nums[m] > target)
            // この場合、target は区間 [i, m) に存在する
            j = m;
        // 目的の要素が見つかったので、そのインデックスを返す
        else return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.ts
/* 二分探索（左閉右開区間） */
function binarySearchLCRO(nums: number[], target: number): number {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    let i = 0,
        j = nums.length;
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while (i < j) {
        // 中央のインデックス m を計算する
        const m = Math.floor(i + (j - i) / 2);
        if (nums[m] < target) {
            // この場合、target は区間 [m+1, j) に存在する
            i = m + 1;
        } else if (nums[m] > target) {
            // この場合、target は区間 [i, m) に存在する
            j = m;
        } else {
            // 目的の要素が見つかったので、そのインデックスを返す
            return m;
        }
    }
    return -1; // 目的の要素が見つからなかったので、-1 を返す
}
binary_search.dart
/* 二分探索（左閉右開区間） */
int binarySearchLCRO(List<int> nums, int target) {
  // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
  int i = 0, j = nums.length;
  // 探索区間が空になるまで繰り返す（i = j のとき空になる）
  while (i < j) {
    int m = i + (j - i) ~/ 2; // 中央のインデックス m を計算する
    if (nums[m] < target) {
      // この場合、target は区間 [m+1, j) に存在する
      i = m + 1;
    } else if (nums[m] > target) {
      // この場合、target は区間 [i, m) に存在する
      j = m;
    } else {
      // 目的の要素が見つかったので、そのインデックスを返す
      return m;
    }
  }
  // 目的の要素が見つからなかったので、-1 を返す
  return -1;
}
binary_search.rs
/* 二分探索（左閉右開区間） */
fn binary_search_lcro(nums: &[i32], target: i32) -> i32 {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    let mut i = 0;
    let mut j = nums.len() as i32;
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while i < j {
        let m = i + (j - i) / 2; // 中央のインデックス m を計算する
        if nums[m as usize] < target {
            // この場合、target は区間 [m+1, j) に存在する
            i = m + 1;
        } else if nums[m as usize] > target {
            // この場合、target は区間 [i, m) に存在する
            j = m;
        } else {
            // 目的の要素が見つかったので、そのインデックスを返す
            return m;
        }
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.c
/* 二分探索（左閉右開区間） */
int binarySearchLCRO(int *nums, int len, int target) {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    int i = 0, j = len;
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while (i < j) {
        int m = i + (j - i) / 2; // 中央のインデックス m を計算する
        if (nums[m] < target)    // この場合、target は区間 [m+1, j) に存在する
            i = m + 1;
        else if (nums[m] > target) // この場合、target は区間 [i, m) に存在する
            j = m;
        else // 目的の要素が見つかったので、そのインデックスを返す
            return m;
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1;
}
binary_search.kt
/* 二分探索（左閉右開区間） */
fun binarySearchLCRO(nums: IntArray, target: Int): Int {
    // 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
    var i = 0
    var j = nums.size
    // 探索区間が空になるまで繰り返す（i = j のとき空になる）
    while (i < j) {
        val m = i + (j - i) / 2 // 中央のインデックス m を計算する
        if (nums[m] < target) // この場合、target は区間 [m+1, j) に存在する
            i = m + 1
        else if (nums[m] > target) // この場合、target は区間 [i, m) に存在する
            j = m
        else  // 目的の要素が見つかったので、そのインデックスを返す
            return m
    }
    // 目的の要素が見つからなかったので、-1 を返す
    return -1
}
binary_search.rb
### 二分探索（左閉右開区間） ###
def binary_search_lcro(nums, target)
  # 左閉右開区間 [0, n) を初期化する。i, j は配列の先頭要素と末尾要素の次をそれぞれ指す
  i, j = 0, nums.length

  # 探索区間が空になるまで繰り返す（i = j のとき空になる）
  while i < j
    # 中央のインデックス m を計算する
    m = (i + j) / 2

    if nums[m] < target
      i = m + 1 # この場合、target は区間 [m+1, j) に存在する
    elsif nums[m] > target
      j = m - 1 # この場合、target は区間 [i, m) に存在する
    else
      return m  # 目的の要素が見つかったので、そのインデックスを返す
    end
  end

  -1  # 目的の要素が見つからなかったので、-1 を返す
end
実行の可視化

図 10-3 のように、区間の表し方が異なると、二分探索の初期化、ループ条件、区間を縮める操作も変わります。

両端を含む閉区間では、左右の境界がどちらも含まれるため、ポインタ \(i\) と \(j\) で区間を縮める操作も対称になります。そのほうが間違いにくいため、一般には両端を含む閉区間で書くことを勧めます。

二つの区間の定義二つの区間の定義

図 10-3   二つの区間の定義

10.1.2   長所と制約

二分探索は時間と空間の両面で優れた性能を持ちます。

  • 二分探索は時間効率が高く、データが多い場合、対数時間の計算量が大きな利点となります。例えば、データの大きさが \(n = 2^{20}\) のとき、線形探索には \(2^{20} = 1048576\) 回の反復が必要ですが、二分探索では \(\log_2 2^{20} = 20\) 回で済みます。
  • 二分探索には追加の領域が不要です。ハッシュ探索など、追加領域を必要とする探索アルゴリズムと比べて、領域を節約できます。

ただし、二分探索はすべての場合に適しているわけではありません。主な理由は次のとおりです。

  • 二分探索は整列済みのデータにしか適用できません。入力が未整列の場合、二分探索のためだけにソートすると割に合いません。ソートの時間計算量は通常 \(O(n \log n)\) で、線形探索や二分探索より大きいためです。また、要素を頻繁に挿入する場合は、整列状態を保つために所定の位置へ挿入する必要があり、その時間計算量 \(O(n)\) も大きな負担となります。
  • 二分探索は配列にしか適用できません。要素に飛び飛びに、つまり非連続にアクセスする必要がありますが、連結リストではその効率が低いため、連結リストやそれに基づくデータ構造には適していません。
  • データが少ない場合は線形探索のほうが高性能です。線形探索は各反復で判定が 1 回だけですが、二分探索では加算 1 回、除算 1 回、判定 1 ~ 3 回、加算（減算）1 回の計 4 ~ 6 回の基本操作が必要です。そのため、データ量 \(n\) が小さいと、線形探索のほうが速くなります。
コメント欄で、考えや質問、ご提案をお寄せください。