コンテンツにスキップ

10.3   二分探索の境界

10.3.1   左端境界を探す

Question

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

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

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

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

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

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\) を得る必要があることに注意してください：

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 は変更不要です）。
ご意見、ご質問、ご提案があればぜひコメントしてください