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\) . Код приведен ниже:
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.
- Выполнить двоичный поиск и получить индекс любого элемента
target, обозначив его как \(k\) . - Начиная с индекса \(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\) и является точкой вставки.
Рисунок 10-6 Шаги поиска точки вставки для повторяющихся элементов
Если посмотреть на следующий код, то видно, что операции в ветвях nums[m] > target и nums[m] == target совпадают, поэтому эти две ветви можно объединить.
Даже в этом случае можно оставить условия развернутыми, потому что так логика выглядит более ясной и код легче читать.
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\) постепенно приближаются к заранее заданной цели. В конце они либо успешно находят ответ, либо останавливаются после выхода за границы.