コンテンツにスキップ
日本語版のレビュアーを募集しています。詳しくは こちら をご覧ください。

# 10.2 二分探索の挿入位置

二分探索は目標要素の検索だけでなく、目標要素の挿入位置を探すなど、多くの派生問題の解決にも利用できます。

## 10.2.1 重複要素がない場合

Question

長さ \(n\) の整列済み配列 `nums` と要素 `target` が与えられます。配列には重複要素は存在しません。ここで `target` を配列 `nums` に挿入し、その順序を保ちます。配列中にすでに要素 `target` が存在する場合は、その左側に挿入します。挿入後の配列における `target` のインデックスを返してください。例を以下の図に示します。

図 10-4 二分探索の挿入位置の例データ

前節の二分探索コードを再利用したい場合は、次の二つの問題に答える必要があります。

問題 1：配列に `target` が含まれる場合、挿入位置のインデックスはその要素のインデックスですか？

問題では `target` を等しい要素の左側に挿入するよう求めているため、新しく挿入された `target` は元の `target` の位置に入ります。つまり、配列に `target` が含まれる場合、挿入位置のインデックスはその `target` のインデックスです。

問題 2：配列に `target` が存在しない場合、挿入位置はどの要素のインデックスですか？

二分探索の過程をさらに考えると、`nums[m] < target` のときは \(i\) が移動します。これは、ポインタ \(i\) が `target` 以上の要素へ近づいていることを意味します。同様に、ポインタ \(j\) は常に `target` 以下の要素へ近づいています。

したがって二分探索の終了時には、\(i\) は `target` より大きい最初の要素を指し、\(j\) は `target` より小さい最も右の要素を指します。よって、配列に `target` が含まれない場合、挿入インデックスは \(i\) です。コードは次のとおりです：

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
binary_search_insertion.py

    def binary_search_insertion_simple(nums: list[int], target: int) -> int:
        """二分探索で挿入位置を探す（重複要素なし）"""
        i, j = 0, len(nums) - 1  # 両閉区間 [0, n-1] を初期化
        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 - 1  # target は区間 [i, m-1] にある
            else:
                return m  # target が見つかったら、挿入位置 m を返す
        # target が見つからなければ、挿入位置 i を返す
        return i

binary_search_insertion.cpp

    /* 二分探索で挿入位置を探す（重複要素なし） */
    int binarySearchInsertionSimple(vector<int> &nums, int target) {
        int i = 0, j = nums.size() - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            int m = i + (j - i) / 2; // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                return m; // target が見つかったら、挿入位置 m を返す
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i;
    }

binary_search_insertion.java

    /* 二分探索で挿入位置を探す（重複要素なし） */
    int binarySearchInsertionSimple(int[] nums, int target) {
        int i = 0, j = nums.length - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            int m = i + (j - i) / 2; // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                return m; // target が見つかったら、挿入位置 m を返す
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i;
    }

binary_search_insertion.cs

    /* 二分探索で挿入位置を探す（重複要素なし） */
    int BinarySearchInsertionSimple(int[] nums, int target) {
        int i = 0, j = nums.Length - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            int m = i + (j - i) / 2; // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                return m; // target が見つかったら、挿入位置 m を返す
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i;
    }

binary_search_insertion.go

    /* 二分探索で挿入位置を探す（重複要素なし） */
    func binarySearchInsertionSimple(nums []int, target int) int {
        // 両閉区間 [0, n-1] を初期化
        i, j := 0, len(nums)-1
        for i <= j {
            // 中点インデックス m を計算
            m := 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 {
                // target が見つかったら、挿入位置 m を返す
                return m
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i
    }

binary_search_insertion.swift

    /* 二分探索で挿入位置を探す（重複要素なし） */
    func binarySearchInsertionSimple(nums: [Int], target: Int) -> Int {
        // 両閉区間 [0, n-1] を初期化
        var i = nums.startIndex
        var j = nums.endIndex - 1
        while i <= j {
            let m = i + (j - i) / 2 // 中点インデックス m を計算
            if nums[m] < target {
                i = m + 1 // target は区間 [m+1, j] にある
            } else if nums[m] > target {
                j = m - 1 // target は区間 [i, m-1] にある
            } else {
                return m // target が見つかったら、挿入位置 m を返す
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i
    }

binary_search_insertion.js

    /* 二分探索で挿入位置を探す（重複要素なし） */
    function binarySearchInsertionSimple(nums, target) {
        let i = 0,
            j = nums.length - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            const m = Math.floor(i + (j - i) / 2); // 中点インデックス m を計算し、Math.floor() で切り捨てる
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                return m; // target が見つかったら、挿入位置 m を返す
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i;
    }

binary_search_insertion.ts

    /* 二分探索で挿入位置を探す（重複要素なし） */
    function binarySearchInsertionSimple(
        nums: Array<number>,
        target: number
    ): number {
        let i = 0,
            j = nums.length - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            const m = Math.floor(i + (j - i) / 2); // 中点インデックス m を計算し、Math.floor() で切り捨てる
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                return m; // target が見つかったら、挿入位置 m を返す
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i;
    }

binary_search_insertion.dart

    /* 二分探索で挿入位置を探す（重複要素なし） */
    int binarySearchInsertionSimple(List<int> nums, int target) {
      int i = 0, j = nums.length - 1; // 両閉区間 [0, n-1] を初期化
      while (i <= j) {
        int m = i + (j - i) ~/ 2; // 中点インデックス m を計算
        if (nums[m] < target) {
          i = m + 1; // target は区間 [m+1, j] にある
        } else if (nums[m] > target) {
          j = m - 1; // target は区間 [i, m-1] にある
        } else {
          return m; // target が見つかったら、挿入位置 m を返す
        }
      }
      // target が見つからなければ、挿入位置 i を返す
      return i;
    }

binary_search_insertion.rs

    /* 二分探索で挿入位置を探す（重複要素なし） */
    fn binary_search_insertion_simple(nums: &[i32], target: i32) -> i32 {
        let (mut i, mut j) = (0, nums.len() as i32 - 1); // 両閉区間 [0, n-1] を初期化
        while i <= j {
            let m = i + (j - i) / 2; // 中点インデックス m を計算
            if nums[m as usize] < target {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if nums[m as usize] > target {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                return m;
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        i
    }

binary_search_insertion.c

    /* 二分探索で挿入位置を探す（重複要素なし） */
    int binarySearchInsertionSimple(int *nums, int numSize, int target) {
        int i = 0, j = numSize - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            int m = i + (j - i) / 2; // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                return m; // target が見つかったら、挿入位置 m を返す
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i;
    }

binary_search_insertion.kt

    /* 二分探索で挿入位置を探す（重複要素なし） */
    fun binarySearchInsertionSimple(nums: IntArray, target: Int): Int {
        var i = 0
        var j = nums.size - 1 // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            val m = i + (j - i) / 2 // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1 // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1 // target は区間 [i, m-1] にある
            } else {
                return m // target が見つかったら、挿入位置 m を返す
            }
        }
        // target が見つからなければ、挿入位置 i を返す
        return i
    }

binary_search_insertion.rb

    ### 二分探索の挿入位置（重複要素なし） ###
    def binary_search_insertion_simple(nums, target)
      # 両閉区間 [0, n-1] を初期化
      i, j = 0, nums.length - 1

      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-1] にある
        else
          return m  # target が見つかったら、挿入位置 m を返す
        end
      end

      i # target が見つからなければ、挿入位置 i を返す
    end

コードの可視化

全画面で見る >

## 10.2.2 重複要素がある場合

Question

前問を踏まえ、配列には重複要素が含まれる可能性があるものとし、それ以外の条件は変わりません。

配列中に複数の `target` が存在する場合、通常の二分探索ではそのうち一つの `target` のインデックスしか返せず、その要素の左側と右側にあといくつ `target` があるかは分かりません。

問題では目標要素を最も左に挿入する必要があるため、配列中で最も左にある `target` のインデックスを探す必要があります。まずは以下の図に示す手順で実現することを考えます。

1. 二分探索を実行し、任意の `target` のインデックスを得て、これを \(k\) とします。
2. インデックス \(k\) から始めて左へ線形探索し、最も左の `target` を見つけたら返します。

図 10-5 線形探索による重複要素の挿入位置

この方法は使用できますが、線形探索を含むため、時間計算量は \(O(n)\) です。配列中に重複した `target` が多い場合、この方法の効率は低くなります。

次に、二分探索のコードを拡張することを考えます。以下の図に示すように、全体の流れは変えず、各反復でまず中点インデックス \(m\) を計算し、その後 `target` と `nums[m]` の大小関係を判定して、次のいくつかの状況に分けます。

- `nums[m] < target` または `nums[m] > target` のときは、まだ `target` を見つけていないことを意味するため、通常の二分探索と同じ区間縮小を行い、ポインタ \(i\) と \(j\) を `target` に近づけます。
- `nums[m] == target` のときは、`target` より小さい要素が区間 \([i, m - 1]\) にあることを意味するため、\(j = m - 1\) として区間を縮小し、ポインタ \(j\) を `target` より小さい要素に近づけます。

ループ終了後、\(i\) は最も左の `target` を指し、\(j\) は `target` より小さい最も右の要素を指すため、インデックス \(i\) が挿入位置です。

<1><2><3><4><5><6><7><8>

図 10-6 重複要素に対する二分探索の挿入位置の手順

以下のコードを観察すると、分岐 `nums[m] > target` と `nums[m] == target` の処理は同じであるため、両者はまとめることができます。

それでも、判定条件を分けたままにしておくことは可能であり、そのほうがロジックがより明確で、可読性も高くなります。

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
binary_search_insertion.py

    def binary_search_insertion(nums: list[int], target: int) -> int:
        """二分探索で挿入位置を探す（重複要素あり）"""
        i, j = 0, len(nums) - 1  # 両閉区間 [0, n-1] を初期化
        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 - 1  # target は区間 [i, m-1] にある
            else:
                j = m - 1  # target より小さい最も右の要素は区間 [i, m-1] にある
        # 挿入位置 i を返す
        return i

binary_search_insertion.cpp

    /* 二分探索で挿入位置を探す（重複要素あり） */
    int binarySearchInsertion(vector<int> &nums, int target) {
        int i = 0, j = nums.size() - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            int m = i + (j - i) / 2; // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                j = m - 1; // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        return i;
    }

binary_search_insertion.java

    /* 二分探索で挿入位置を探す（重複要素あり） */
    int binarySearchInsertion(int[] nums, int target) {
        int i = 0, j = nums.length - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            int m = i + (j - i) / 2; // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                j = m - 1; // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        return i;
    }

binary_search_insertion.cs

    /* 二分探索で挿入位置を探す（重複要素あり） */
    int BinarySearchInsertion(int[] nums, int target) {
        int i = 0, j = nums.Length - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            int m = i + (j - i) / 2; // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                j = m - 1; // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        return i;
    }

binary_search_insertion.go

    /* 二分探索で挿入位置を探す（重複要素あり） */
    func binarySearchInsertion(nums []int, target int) int {
        // 両閉区間 [0, n-1] を初期化
        i, j := 0, len(nums)-1
        for i <= j {
            // 中点インデックス m を計算
            m := 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 {
                // target より小さい最も右の要素は区間 [i, m-1] にある
                j = m - 1
            }
        }
        // 挿入位置 i を返す
        return i
    }

binary_search_insertion.swift

    /* 二分探索で挿入位置を探す（重複要素あり） */
    func binarySearchInsertion(nums: [Int], target: Int) -> Int {
        // 両閉区間 [0, n-1] を初期化
        var i = nums.startIndex
        var j = nums.endIndex - 1
        while i <= j {
            let m = i + (j - i) / 2 // 中点インデックス m を計算
            if nums[m] < target {
                i = m + 1 // target は区間 [m+1, j] にある
            } else if nums[m] > target {
                j = m - 1 // target は区間 [i, m-1] にある
            } else {
                j = m - 1 // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        return i
    }

binary_search_insertion.js

    /* 二分探索で挿入位置を探す（重複要素あり） */
    function binarySearchInsertion(nums, target) {
        let i = 0,
            j = nums.length - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            const m = Math.floor(i + (j - i) / 2); // 中点インデックス m を計算し、Math.floor() で切り捨てる
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                j = m - 1; // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        return i;
    }

binary_search_insertion.ts

    /* 二分探索で挿入位置を探す（重複要素あり） */
    function binarySearchInsertion(nums: Array<number>, target: number): number {
        let i = 0,
            j = nums.length - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            const m = Math.floor(i + (j - i) / 2); // 中点インデックス m を計算し、Math.floor() で切り捨てる
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                j = m - 1; // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        return i;
    }

binary_search_insertion.dart

    /* 二分探索で挿入位置を探す（重複要素あり） */
    int binarySearchInsertion(List<int> nums, int target) {
      int i = 0, j = nums.length - 1; // 両閉区間 [0, n-1] を初期化
      while (i <= j) {
        int m = i + (j - i) ~/ 2; // 中点インデックス m を計算
        if (nums[m] < target) {
          i = m + 1; // target は区間 [m+1, j] にある
        } else if (nums[m] > target) {
          j = m - 1; // target は区間 [i, m-1] にある
        } else {
          j = m - 1; // target より小さい最も右の要素は区間 [i, m-1] にある
        }
      }
      // 挿入位置 i を返す
      return i;
    }

binary_search_insertion.rs

    /* 二分探索で挿入位置を探す（重複要素あり） */
    pub fn binary_search_insertion(nums: &[i32], target: i32) -> i32 {
        let (mut i, mut j) = (0, nums.len() as i32 - 1); // 両閉区間 [0, n-1] を初期化
        while i <= j {
            let m = i + (j - i) / 2; // 中点インデックス m を計算
            if nums[m as usize] < target {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if nums[m as usize] > target {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                j = m - 1; // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        i
    }

binary_search_insertion.c

    /* 二分探索で挿入位置を探す（重複要素あり） */
    int binarySearchInsertion(int *nums, int numSize, int target) {
        int i = 0, j = numSize - 1; // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            int m = i + (j - i) / 2; // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1; // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1; // target は区間 [i, m-1] にある
            } else {
                j = m - 1; // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        return i;
    }

binary_search_insertion.kt

    /* 二分探索で挿入位置を探す（重複要素あり） */
    fun binarySearchInsertion(nums: IntArray, target: Int): Int {
        var i = 0
        var j = nums.size - 1 // 両閉区間 [0, n-1] を初期化
        while (i <= j) {
            val m = i + (j - i) / 2 // 中点インデックス m を計算
            if (nums[m] < target) {
                i = m + 1 // target は区間 [m+1, j] にある
            } else if (nums[m] > target) {
                j = m - 1 // target は区間 [i, m-1] にある
            } else {
                j = m - 1 // target より小さい最も右の要素は区間 [i, m-1] にある
            }
        }
        // 挿入位置 i を返す
        return i
    }

binary_search_insertion.rb

    ### 二分探索の挿入位置（重複要素あり） ###
    def binary_search_insertion(nums, target)
      # 両閉区間 [0, n-1] を初期化
      i, j = 0, nums.length - 1

      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-1] にある
        else
          j = m - 1 # target より小さい最も右の要素は区間 [i, m-1] にある
        end
      end

      i # 挿入位置 i を返す
    end

コードの可視化

全画面で見る >

Tip

本節のコードはすべて「両閉区間」の書き方です。興味のある読者は「左閉右開」の書き方を自分で実装してみてください。

要するに、二分探索とはポインタ \(i\) と \(j\) にそれぞれ探索目標を設定することにほかなりません。目標は具体的な要素（たとえば `target`）である場合もあれば、要素の範囲（たとえば `target` より小さい要素）である場合もあります。

繰り返される二分のループの中で、ポインタ \(i\) と \(j\) はどちらも事前に定めた目標へ徐々に近づいていきます。最終的に、それらは答えを見つけるか、境界を越えたところで停止します。

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