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

# 10.3 二分探索の境界

## 10.3.1 左端境界を探す

Question

長さ \(n\) のソート済み配列 `nums` が与えられ、その中には重複要素が含まれる可能性があります。配列内で最も左にある要素 `target` のインデックスを返してください。配列にこの要素が含まれない場合は、\(-1\) を返します。

二分探索で挿入位置を求める方法を思い出すと、探索完了後に \(i\) は最も左にある `target` を指します。したがって、挿入位置を探すことの本質は、最も左にある `target` のインデックスを探すことです。

挿入位置を探す関数を使って左端境界を求めることを考えます。なお、配列に `target` が含まれない場合があり、そのときは次の 2 つの結果が起こりえます。

- 挿入位置のインデックス \(i\) が範囲外になる。
- 要素 `nums[i]` が `target` と等しくない。

上の 2 つの状況に当てはまる場合は、直接 \(-1\) を返せば十分です。コードは以下のとおりです：

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

    def binary_search_left_edge(nums: list[int], target: int) -> int:
        """最も左の target を二分探索"""
        # target の挿入位置を探すのと等価
        i = binary_search_insertion(nums, target)
        # target が見つからなければ、-1 を返す
        if i == len(nums) or nums[i] != target:
            return -1
        # target が見つかったら、インデックス i を返す
        return i

binary_search_edge.cpp

    /* 最も左の target を二分探索 */
    int binarySearchLeftEdge(vector<int> &nums, int target) {
        // target の挿入位置を探すのと等価
        int i = binarySearchInsertion(nums, target);
        // target が見つからなければ、-1 を返す
        if (i == nums.size() || nums[i] != target) {
            return -1;
        }
        // target が見つかったら、インデックス i を返す
        return i;
    }

binary_search_edge.java

    /* 最も左の target を二分探索 */
    int binarySearchLeftEdge(int[] nums, int target) {
        // target の挿入位置を探すのと等価
        int i = binary_search_insertion.binarySearchInsertion(nums, target);
        // target が見つからなければ、-1 を返す
        if (i == nums.length || nums[i] != target) {
            return -1;
        }
        // target が見つかったら、インデックス i を返す
        return i;
    }

binary_search_edge.cs

    /* 最も左の target を二分探索 */
    int BinarySearchLeftEdge(int[] nums, int target) {
        // target の挿入位置を探すのと等価
        int i = binary_search_insertion.BinarySearchInsertion(nums, target);
        // target が見つからなければ、-1 を返す
        if (i == nums.Length || nums[i] != target) {
            return -1;
        }
        // target が見つかったら、インデックス i を返す
        return i;
    }

binary_search_edge.go

    /* 最も左の target を二分探索 */
    func binarySearchLeftEdge(nums []int, target int) int {
        // target の挿入位置を探すのと等価
        i := binarySearchInsertion(nums, target)
        // target が見つからなければ、-1 を返す
        if i == len(nums) || nums[i] != target {
            return -1
        }
        // target が見つかったら、インデックス i を返す
        return i
    }

binary_search_edge.swift

    /* 最も左の target を二分探索 */
    func binarySearchLeftEdge(nums: [Int], target: Int) -> Int {
        // target の挿入位置を探すのと等価
        let i = binarySearchInsertion(nums: nums, target: target)
        // target が見つからなければ、-1 を返す
        if i == nums.endIndex || nums[i] != target {
            return -1
        }
        // target が見つかったら、インデックス i を返す
        return i
    }

binary_search_edge.js

    /* 最も左の target を二分探索 */
    function binarySearchLeftEdge(nums, target) {
        // target の挿入位置を探すのと等価
        const i = binarySearchInsertion(nums, target);
        // target が見つからなければ、-1 を返す
        if (i === nums.length || nums[i] !== target) {
            return -1;
        }
        // target が見つかったら、インデックス i を返す
        return i;
    }

binary_search_edge.ts

    /* 最も左の target を二分探索 */
    function binarySearchLeftEdge(nums: Array<number>, target: number): number {
        // target の挿入位置を探すのと等価
        const i = binarySearchInsertion(nums, target);
        // target が見つからなければ、-1 を返す
        if (i === nums.length || nums[i] !== target) {
            return -1;
        }
        // target が見つかったら、インデックス i を返す
        return i;
    }

binary_search_edge.dart

    /* 最も左の target を二分探索 */
    int binarySearchLeftEdge(List<int> nums, int target) {
      // target の挿入位置を探すのと等価
      int i = binarySearchInsertion(nums, target);
      // target が見つからなければ、-1 を返す
      if (i == nums.length || nums[i] != target) {
        return -1;
      }
      // target が見つかったら、インデックス i を返す
      return i;
    }

binary_search_edge.rs

    /* 最も左の target を二分探索 */
    fn binary_search_left_edge(nums: &[i32], target: i32) -> i32 {
        // target の挿入位置を探すのと等価
        let i = binary_search_insertion(nums, target);
        // target が見つからなければ、-1 を返す
        if i == nums.len() as i32 || nums[i as usize] != target {
            return -1;
        }
        // target が見つかったら、インデックス i を返す
        i
    }

binary_search_edge.c

    /* 最も左の target を二分探索 */
    int binarySearchLeftEdge(int *nums, int numSize, int target) {
        // target の挿入位置を探すのと等価
        int i = binarySearchInsertion(nums, numSize, target);
        // target が見つからなければ、-1 を返す
        if (i == numSize || nums[i] != target) {
            return -1;
        }
        // target が見つかったら、インデックス i を返す
        return i;
    }

binary_search_edge.kt

    /* 最も左の target を二分探索 */
    fun binarySearchLeftEdge(nums: IntArray, target: Int): Int {
        // target の挿入位置を探すのと等価
        val i = binarySearchInsertion(nums, target)
        // target が見つからなければ、-1 を返す
        if (i == nums.size || nums[i] != target) {
            return -1
        }
        // target が見つかったら、インデックス i を返す
        return i
    }

binary_search_edge.rb

    ### target の最左位置を二分探索 ###
    def binary_search_left_edge(nums, target)
      # target の挿入位置を探すのと等価
      i = binary_search_insertion(nums, target)

      # target が見つからなければ、-1 を返す
      return -1 if i == nums.length || nums[i] != target

      i # target が見つかったら、インデックス i を返す
    end

コードの可視化

全画面で見る >

## 10.3.2 右端境界を探す

では、最も右にある `target` はどのように探せるでしょうか。最も直接的な方法はコードを修正し、`nums[m] == target` の場合のポインタの縮小操作を置き換えることです。ここではコードを省略するので、興味があれば自分で実装してみてください。

ここでは、より巧妙な 2 つの方法を紹介します。

### 1. 左端境界探索を再利用する

実際には、最も左の要素を探す関数を利用して最も右の要素を探せます。具体的には、最も右にある `target` を探すことを、最も左にある `target + 1` を探すことに変換します。

下図のように、探索完了後、ポインタ \(i\) は最も左にある `target + 1`（存在する場合）を指し、\(j\) は最も右にある `target` を指します。したがって \(j\) を返せばよいです。

図 10-7 右端境界の探索を左端境界の探索に変換する

返される挿入位置は \(i\) なので、そこから \(1\) を引いて \(j\) を得る必要があることに注意してください：

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

    def binary_search_right_edge(nums: list[int], target: int) -> int:
        """最も右の target を二分探索"""
        # 最左の target + 1 を探す問題に変換する
        i = binary_search_insertion(nums, target + 1)
        # j は最も右の target を指し、i は target より大きい最初の要素を指す
        j = i - 1
        # target が見つからなければ、-1 を返す
        if j == -1 or nums[j] != target:
            return -1
        # target が見つかったら、インデックス j を返す
        return j

binary_search_edge.cpp

    /* 最も右の target を二分探索 */
    int binarySearchRightEdge(vector<int> &nums, int target) {
        // 最左の target + 1 を探す問題に変換する
        int i = binarySearchInsertion(nums, target + 1);
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        int j = i - 1;
        // target が見つからなければ、-1 を返す
        if (j == -1 || nums[j] != target) {
            return -1;
        }
        // target が見つかったら、インデックス j を返す
        return j;
    }

binary_search_edge.java

    /* 最も右の target を二分探索 */
    int binarySearchRightEdge(int[] nums, int target) {
        // 最左の target + 1 を探す問題に変換する
        int i = binary_search_insertion.binarySearchInsertion(nums, target + 1);
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        int j = i - 1;
        // target が見つからなければ、-1 を返す
        if (j == -1 || nums[j] != target) {
            return -1;
        }
        // target が見つかったら、インデックス j を返す
        return j;
    }

binary_search_edge.cs

    /* 最も右の target を二分探索 */
    int BinarySearchRightEdge(int[] nums, int target) {
        // 最左の target + 1 を探す問題に変換する
        int i = binary_search_insertion.BinarySearchInsertion(nums, target + 1);
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        int j = i - 1;
        // target が見つからなければ、-1 を返す
        if (j == -1 || nums[j] != target) {
            return -1;
        }
        // target が見つかったら、インデックス j を返す
        return j;
    }

binary_search_edge.go

    /* 最も右の target を二分探索 */
    func binarySearchRightEdge(nums []int, target int) int {
        // 最左の target + 1 を探す問題に変換する
        i := binarySearchInsertion(nums, target+1)
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        j := i - 1
        // target が見つからなければ、-1 を返す
        if j == -1 || nums[j] != target {
            return -1
        }
        // target が見つかったら、インデックス j を返す
        return j
    }

binary_search_edge.swift

    /* 最も右の target を二分探索 */
    func binarySearchRightEdge(nums: [Int], target: Int) -> Int {
        // 最左の target + 1 を探す問題に変換する
        let i = binarySearchInsertion(nums: nums, target: target + 1)
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        let j = i - 1
        // target が見つからなければ、-1 を返す
        if j == -1 || nums[j] != target {
            return -1
        }
        // target が見つかったら、インデックス j を返す
        return j
    }

binary_search_edge.js

    /* 最も右の target を二分探索 */
    function binarySearchRightEdge(nums, target) {
        // 最左の target + 1 を探す問題に変換する
        const i = binarySearchInsertion(nums, target + 1);
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        const j = i - 1;
        // target が見つからなければ、-1 を返す
        if (j === -1 || nums[j] !== target) {
            return -1;
        }
        // target が見つかったら、インデックス j を返す
        return j;
    }

binary_search_edge.ts

    /* 最も右の target を二分探索 */
    function binarySearchRightEdge(nums: Array<number>, target: number): number {
        // 最左の target + 1 を探す問題に変換する
        const i = binarySearchInsertion(nums, target + 1);
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        const j = i - 1;
        // target が見つからなければ、-1 を返す
        if (j === -1 || nums[j] !== target) {
            return -1;
        }
        // target が見つかったら、インデックス j を返す
        return j;
    }

binary_search_edge.dart

    /* 最も右の target を二分探索 */
    int binarySearchRightEdge(List<int> nums, int target) {
      // 最左の target + 1 を探す問題に変換する
      int i = binarySearchInsertion(nums, target + 1);
      // j は最も右の target を指し、i は target より大きい最初の要素を指す
      int j = i - 1;
      // target が見つからなければ、-1 を返す
      if (j == -1 || nums[j] != target) {
        return -1;
      }
      // target が見つかったら、インデックス j を返す
      return j;
    }

binary_search_edge.rs

    /* 最も右の target を二分探索 */
    fn binary_search_right_edge(nums: &[i32], target: i32) -> i32 {
        // 最左の target + 1 を探す問題に変換する
        let i = binary_search_insertion(nums, target + 1);
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        let j = i - 1;
        // target が見つからなければ、-1 を返す
        if j == -1 || nums[j as usize] != target {
            return -1;
        }
        // target が見つかったら、インデックス j を返す
        j
    }

binary_search_edge.c

    /* 最も右の target を二分探索 */
    int binarySearchRightEdge(int *nums, int numSize, int target) {
        // 最左の target + 1 を探す問題に変換する
        int i = binarySearchInsertion(nums, numSize, target + 1);
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        int j = i - 1;
        // target が見つからなければ、-1 を返す
        if (j == -1 || nums[j] != target) {
            return -1;
        }
        // target が見つかったら、インデックス j を返す
        return j;
    }

binary_search_edge.kt

    /* 最も右の target を二分探索 */
    fun binarySearchRightEdge(nums: IntArray, target: Int): Int {
        // 最左の target + 1 を探す問題に変換する
        val i = binarySearchInsertion(nums, target + 1)
        // j は最も右の target を指し、i は target より大きい最初の要素を指す
        val j = i - 1
        // target が見つからなければ、-1 を返す
        if (j == -1 || nums[j] != target) {
            return -1
        }
        // target が見つかったら、インデックス j を返す
        return j
    }

binary_search_edge.rb

    ### target の最右位置を二分探索 ###
    def binary_search_right_edge(nums, target)
      # 最左の target + 1 を探す問題に変換する
      i = binary_search_insertion(nums, target + 1)

      # j は最も右の target を指し、i は target より大きい最初の要素を指す
      j = i - 1

      # target が見つからなければ、-1 を返す
      return -1 if j == -1 || nums[j] != target

      j # target が見つかったら、インデックス j を返す
    end

コードの可視化

全画面で見る >

### 2. 要素探索に変換する

配列に `target` が含まれない場合、最終的に \(i\) と \(j\) はそれぞれ `target` より大きい最初の要素と、`target` より小さい最も右の要素を指すことになります。

したがって、下図のように、配列中に存在しない要素を構成して、それを使って左右の境界を探せます。

- 最も左にある `target` の探索：`target - 0.5` を探すことに変換でき、ポインタ \(i\) を返します。
- 最も右にある `target` の探索：`target + 0.5` を探すことに変換でき、ポインタ \(j\) を返します。

図 10-8 境界の探索を要素の探索に変換する

ここではコードを省略しますが、次の 2 点に注意が必要です。

- 与えられた配列には小数が含まれないため、等しい場合をどう処理するかを気にする必要はありません。
- この方法では小数を導入するため、関数内の変数 `target` を浮動小数点数型に変更する必要があります（Python は変更不要です）。

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