Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

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

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

Question

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

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

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

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

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

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

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

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

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

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

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

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

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

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

##### Оставляйте свои идеи, вопросы и предложения в комментариях