12.2 分割統治探索戦略¶

私たちはすでに学んだように、探索アルゴリズムは大きく二つに分けられる。

力ずく探索：データ構造を走査することで実現され、時間計算量は \(O(n)\) である。
適応的探索：固有のデータ構造や事前情報を利用し、時間計算量は \(O(\log n)\) 、さらには \(O(1)\) に達しうる。

実際、時間計算量が \(O(\log n)\) の探索アルゴリズムは通常、分割統治戦略に基づいて実装される。たとえば二分探索や木構造である。

二分探索の各ステップでは、問題（配列内で目標要素を探索すること）を小さな問題（配列の半分で目標要素を探索すること）に分解し、この過程は配列が空になるか目標要素が見つかるまで続く。
木構造は分割統治の考え方を代表するものであり、二分探索木、AVL 木、ヒープなどのデータ構造では、さまざまな操作の時間計算量はいずれも \(O(\log n)\) である。

二分探索の分割統治戦略は以下のとおりである。

問題は分解できる：二分探索は、元の問題（配列内で探索すること）を部分問題（配列の半分で探索すること）へ再帰的に分解する。これは中央要素と目標要素を比較することで実現される。
部分問題は独立している：二分探索では、各ラウンドで一つの部分問題だけを処理し、ほかの部分問題の影響を受けない。
部分問題の解を統合する必要はない：二分探索は特定の要素を探すことを目的としているため、部分問題の解を統合する必要がない。部分問題が解決されると、元の問題も同時に解決される。

分割統治が探索効率を高められる本質的な理由は、力ずく探索では各ラウンドで一つの候補しか除外できないのに対し、**分割統治による探索では各ラウンドで候補の半分を除外できる**からである。

1. 分割統治に基づく二分探索¶

前の章では、二分探索を漸化式（反復）に基づいて実装した。ここでは分割統治（再帰）に基づいてこれを実装する。

Question

長さ \(n\) の昇順配列 nums が与えられ、そのすべての要素は一意である。要素 target を探索せよ。

分割統治の観点から、探索区間 \([i, j]\) に対応する部分問題を \(f(i, j)\) と記す。

元の問題 \(f(0, n-1)\) を出発点として、次の手順で二分探索を行う。

探索区間 \([i, j]\) の中点 \(m\) を計算し、それに基づいて探索区間の半分を除外する。
規模が半分に縮小された部分問題を再帰的に解く。候補は \(f(i, m-1)\) または \(f(m+1, j)\) である。
1. と 2. の手順を繰り返し、target が見つかるか区間が空になったら返す。

次の図は、配列内で要素 \(6\) を二分探索する分割統治の過程を示している。

二分探索の分割統治の過程

図 12-4 二分探索の分割統治の過程

実装コードでは、再帰関数 dfs() を宣言して問題 \(f(i, j)\) を解く。

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search_recur.py

def dfs(nums: list[int], target: int, i: int, j: int) -> int:
    """二分探索：問題 f(i, j)"""
    # 区間が空なら対象要素は存在しないので -1 を返す
    if i > j:
        return -1
    # 中点インデックス m を計算
    m = (i + j) // 2
    if nums[m] < target:
        # 部分問題 f(m+1, j) を再帰的に解く
        return dfs(nums, target, m + 1, j)
    elif nums[m] > target:
        # 部分問題 f(i, m-1) を再帰的に解く
        return dfs(nums, target, i, m - 1)
    else:
        # 目標要素が見つかったらそのインデックスを返す
        return m

def binary_search(nums: list[int], target: int) -> int:
    """二分探索"""
    n = len(nums)
    # 問題 f(0, n-1) を解く
    return dfs(nums, target, 0, n - 1)

binary_search_recur.cpp

/* 二分探索：問題 f(i, j) */
int dfs(vector<int> &nums, int target, int i, int j) {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if (i > j) {
        return -1;
    }
    // 中点インデックス m を計算
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // 部分問題 f(m+1, j) を再帰的に解く
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 部分問題 f(i, m-1) を再帰的に解く
        return dfs(nums, target, i, m - 1);
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m;
    }
}

/* 二分探索 */
int binarySearch(vector<int> &nums, int target) {
    int n = nums.size();
    // 問題 f(0, n-1) を解く
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.java

/* 二分探索：問題 f(i, j) */
int dfs(int[] nums, int target, int i, int j) {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if (i > j) {
        return -1;
    }
    // 中点インデックス m を計算
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // 部分問題 f(m+1, j) を再帰的に解く
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 部分問題 f(i, m-1) を再帰的に解く
        return dfs(nums, target, i, m - 1);
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m;
    }
}

/* 二分探索 */
int binarySearch(int[] nums, int target) {
    int n = nums.length;
    // 問題 f(0, n-1) を解く
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.cs

/* 二分探索：問題 f(i, j) */
int DFS(int[] nums, int target, int i, int j) {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if (i > j) {
        return -1;
    }
    // 中点インデックス m を計算
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // 部分問題 f(m+1, j) を再帰的に解く
        return DFS(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 部分問題 f(i, m-1) を再帰的に解く
        return DFS(nums, target, i, m - 1);
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m;
    }
}

/* 二分探索 */
int BinarySearch(int[] nums, int target) {
    int n = nums.Length;
    // 問題 f(0, n-1) を解く
    return DFS(nums, target, 0, n - 1);
}

binary_search_recur.go

/* 二分探索：問題 f(i, j) */
func dfs(nums []int, target, i, j int) int {
    // 区間が空なら対象要素は存在しないため、-1 を返す
    if i > j {
        return -1
    }
    // 中点インデックスを計算する
    m := i + ((j - i) >> 1)
    // 中点の要素と目標要素の大小を判定する
    if nums[m] < target {
        // 小さければ右半分の配列を再帰
        // 部分問題 f(m+1, j) を解く
        return dfs(nums, target, m+1, j)
    } else if nums[m] > target {
        // 大きければ左半分の配列を再帰
        // 部分問題 f(i, m-1) を解く
        return dfs(nums, target, i, m-1)
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m
    }
}

/* 二分探索 */
func binarySearch(nums []int, target int) int {
    n := len(nums)
    return dfs(nums, target, 0, n-1)
}

binary_search_recur.swift

/* 二分探索：問題 f(i, j) */
func dfs(nums: [Int], target: Int, i: Int, j: Int) -> Int {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if i > j {
        return -1
    }
    // 中点インデックス m を計算
    let m = (i + j) / 2
    if nums[m] < target {
        // 部分問題 f(m+1, j) を再帰的に解く
        return dfs(nums: nums, target: target, i: m + 1, j: j)
    } else if nums[m] > target {
        // 部分問題 f(i, m-1) を再帰的に解く
        return dfs(nums: nums, target: target, i: i, j: m - 1)
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m
    }
}

/* 二分探索 */
func binarySearch(nums: [Int], target: Int) -> Int {
    // 問題 f(0, n-1) を解く
    dfs(nums: nums, target: target, i: nums.startIndex, j: nums.endIndex - 1)
}

binary_search_recur.js

/* 二分探索：問題 f(i, j) */
function dfs(nums, target, i, j) {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if (i > j) {
        return -1;
    }
    // 中点インデックス m を計算
    const m = i + ((j - i) >> 1);
    if (nums[m] < target) {
        // 部分問題 f(m+1, j) を再帰的に解く
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 部分問題 f(i, m-1) を再帰的に解く
        return dfs(nums, target, i, m - 1);
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m;
    }
}

/* 二分探索 */
function binarySearch(nums, target) {
    const n = nums.length;
    // 問題 f(0, n-1) を解く
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.ts

/* 二分探索：問題 f(i, j) */
function dfs(nums: number[], target: number, i: number, j: number): number {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if (i > j) {
        return -1;
    }
    // 中点インデックス m を計算
    const m = i + ((j - i) >> 1);
    if (nums[m] < target) {
        // 部分問題 f(m+1, j) を再帰的に解く
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 部分問題 f(i, m-1) を再帰的に解く
        return dfs(nums, target, i, m - 1);
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m;
    }
}

/* 二分探索 */
function binarySearch(nums: number[], target: number): number {
    const n = nums.length;
    // 問題 f(0, n-1) を解く
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.dart

/* 二分探索：問題 f(i, j) */
int dfs(List<int> nums, int target, int i, int j) {
  // 区間が空なら対象要素は存在しないので -1 を返す
  if (i > j) {
    return -1;
  }
  // 中点インデックス m を計算
  int m = (i + j) ~/ 2;
  if (nums[m] < target) {
    // 部分問題 f(m+1, j) を再帰的に解く
    return dfs(nums, target, m + 1, j);
  } else if (nums[m] > target) {
    // 部分問題 f(i, m-1) を再帰的に解く
    return dfs(nums, target, i, m - 1);
  } else {
    // 目標要素が見つかったらそのインデックスを返す
    return m;
  }
}

/* 二分探索 */
int binarySearch(List<int> nums, int target) {
  int n = nums.length;
  // 問題 f(0, n-1) を解く
  return dfs(nums, target, 0, n - 1);
}

binary_search_recur.rs

/* 二分探索：問題 f(i, j) */
fn dfs(nums: &[i32], target: i32, i: i32, j: i32) -> i32 {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if i > j {
        return -1;
    }
    let m: i32 = i + (j - i) / 2;
    if nums[m as usize] < target {
        // 部分問題 f(m+1, j) を再帰的に解く
        return dfs(nums, target, m + 1, j);
    } else if nums[m as usize] > target {
        // 部分問題 f(i, m-1) を再帰的に解く
        return dfs(nums, target, i, m - 1);
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m;
    }
}

/* 二分探索 */
fn binary_search(nums: &[i32], target: i32) -> i32 {
    let n = nums.len() as i32;
    // 問題 f(0, n-1) を解く
    dfs(nums, target, 0, n - 1)
}

binary_search_recur.c

/* 二分探索：問題 f(i, j) */
int dfs(int nums[], int target, int i, int j) {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if (i > j) {
        return -1;
    }
    // 中点インデックス m を計算
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // 部分問題 f(m+1, j) を再帰的に解く
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 部分問題 f(i, m-1) を再帰的に解く
        return dfs(nums, target, i, m - 1);
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        return m;
    }
}

/* 二分探索 */
int binarySearch(int nums[], int target, int numsSize) {
    int n = numsSize;
    // 問題 f(0, n-1) を解く
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.kt

/* 二分探索：問題 f(i, j) */
fun dfs(
    nums: IntArray,
    target: Int,
    i: Int,
    j: Int
): Int {
    // 区間が空なら対象要素は存在しないので -1 を返す
    if (i > j) {
        return -1
    }
    // 中点インデックス m を計算
    val m = (i + j) / 2
    return if (nums[m] < target) {
        // 部分問題 f(m+1, j) を再帰的に解く
        dfs(nums, target, m + 1, j)
    } else if (nums[m] > target) {
        // 部分問題 f(i, m-1) を再帰的に解く
        dfs(nums, target, i, m - 1)
    } else {
        // 目標要素が見つかったらそのインデックスを返す
        m
    }
}

/* 二分探索 */
fun binarySearch(nums: IntArray, target: Int): Int {
    val n = nums.size
    // 問題 f(0, n-1) を解く
    return dfs(nums, target, 0, n - 1)
}

binary_search_recur.rb

### 二分探索: 問題 f(i, j) ###
def dfs(nums, target, i, j)
  # 区間が空なら対象要素は存在しないので -1 を返す
  return -1 if i > j

  # 中点インデックス m を計算
  m = (i + j) / 2

  if nums[m] < target
    # 部分問題 f(m+1, j) を再帰的に解く
    return dfs(nums, target, m + 1, j)
  elsif nums[m] > target
    # 部分問題 f(i, m-1) を再帰的に解く
    return dfs(nums, target, i, m - 1)
  else
    # 目標要素が見つかったらそのインデックスを返す
    return m
  end
end

### 二分探索 ###
def binary_search(nums, target)
  n = nums.length
  # 問題 f(0, n-1) を解く
  dfs(nums, target, 0, n - 1)
end

コードの可視化

全画面で見る >

12.2 分割統治探索戦略¶

1. 分割統治に基づく二分探索¶

ご意見、ご質問、ご提案があればぜひコメントしてください