Перейти к содержанию

10.3   Двоичный поиск границ

10.3.1   Поиск левой границы

Question

Дан упорядоченный массив nums длины \(n\), который может содержать повторяющиеся элементы. Верните индекс самого левого элемента target в массиве. Если массив не содержит этот элемент, верните \(-1\) .

Вспомним метод поиска точки вставки при двоичном поиске: после завершения поиска указатель \(i\) указывает на самый левый target , поэтому поиск точки вставки по сути и есть поиск индекса самого левого target.

Рассмотрим реализацию поиска левой границы через функцию поиска точки вставки. Обратите внимание: массив может не содержать target , и тогда возможны две ситуации.

  • Индекс точки вставки \(i\) выходит за границы массива.
  • Элемент nums[i] не равен target .

Если возникает любая из этих ситуаций, достаточно сразу вернуть \(-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 . Мы не будем приводить этот код, заинтересованные читатели могут реализовать его самостоятельно.

Ниже представлены два более изящных способа.

1.   Повторное использование поиска левой границы

На самом деле функцию поиска самого левого элемента можно использовать и для поиска самого правого элемента. Конкретная идея такова: преобразовать поиск самого правого target в поиск самого левого target + 1.

Как показано на рисунке 10-7, после завершения поиска указатель \(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 .

Следовательно, как показано на рисунке 10-8, для поиска левой и правой границы можно сконструировать элемент, которого нет в массиве.

  • Поиск самого левого target : можно преобразовать в поиск target - 0.5 и вернуть указатель \(i\) .
  • Поиск самого правого target : можно преобразовать в поиск target + 0.5 и вернуть указатель \(j\) .

Преобразование поиска границ в поиск элемента

Рисунок 10-8   Преобразование поиска границ в поиск элемента

Код здесь опущен, но стоит обратить внимание на два момента.

  • По условию массив не содержит дробных чисел, поэтому нам не нужно беспокоиться о том, как обрабатывать случай равенства другим элементам массива.
  • Поскольку этот метод вводит дробные числа, переменную target в функции нужно изменить на тип с плавающей запятой (в Python менять ничего не требуется).
Оставляйте свои идеи, вопросы и предложения в комментариях