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

# 10.2 Двоичный поиск точки вставки

Двоичный поиск можно использовать не только для поиска целевого элемента, но и для решения многих вариаций задачи, например для поиска позиции вставки целевого элемента.

## 10.2.1 Случай без повторяющихся элементов

Question

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

Рисунок 10-4 Пример данных для точки вставки

Если мы хотим переиспользовать код двоичного поиска из предыдущего раздела, нужно ответить на два вопроса.

Вопрос 1: если массив содержит `target` , будет ли индекс вставки совпадать с индексом этого элемента?

По условию `target` нужно вставить слева от равного элемента, а это означает, что новый `target` занимает место старого `target` . Иначе говоря, если массив содержит `target` , то индекс вставки совпадает с индексом этого `target`.

Вопрос 2: если массив не содержит `target` , индекс какого элемента будет точкой вставки?

Рассмотрим процесс двоичного поиска подробнее: когда `nums[m] < target` , указатель \(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` в массиве. На первом этапе можно рассмотреть решение, показанное на рисунке 10-5.

1. Выполнить двоичный поиск и получить индекс любого элемента `target` , обозначив его как \(k\) .
2. Начиная с индекса \(k\) , линейно двигаться влево и вернуть результат, когда будет найден самый левый `target` .

Рисунок 10-5 Линейный поиск точки вставки среди повторяющихся элементов

Этот метод применим на практике, однако в нем есть линейный поиск, поэтому его временная сложность равна \(O(n)\) . Когда в массиве имеется много повторяющихся `target` , такой подход работает неэффективно.

Теперь рассмотрим расширение кода двоичного поиска. Как показано на рисунке 10-6, общий процесс остается прежним: на каждом шаге мы сначала вычисляем индекс середины \(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\) постепенно приближаются к заранее заданной цели. В конце они либо успешно находят ответ, либо останавливаются после выхода за границы.

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