Универсальный бинарный поиск

В этом уроке ты

Научишься искать первую и последнюю позицию элемента в отсортированном массиве.
Разберёшься с концепцией “хороших” и “плохих” элементов, которую можно применять в сложных задачах.
Освоишь универсальный шаблон бинарного поиска и научишься адаптировать его под любые цели.

Виды бинарного поиска

Часто нам нужно не просто узнать, есть ли число x в массиве, а найти его индекс (или несколько индексов, если элемент встречается не один раз). Например, если массив — это [2, 7, 7, 7, 7, 8, 9], и мы ищем 7, то можем захотеть найти:

Первое вхождение 7-ки
Последнее вхождение 7-ки

В большинстве задач по бинарному поиску нужно уметь находить либо первое вхождение элемента, либо последнее.

Концепция “хорошего” и “плохого” элемента

Чтобы не запутаться в разных вариантах — ищем ли мы первое или последнее вхождение, — полезно освоить концепцию “хорошего” и “плохого” элемента.

Суть идеи такая:

Мы делим все элементы массива на “хорошие” и “плохие” в зависимости от условия, которое нам нужно найти.
Ищем границу, где заканчиваются “хорошие” элементы и начинаются “плохие” (или наоборот).

Выглядит загадочно, но на практике очень удобно! Ведь с помощью такого подхода можно применять метод бинарного поиска даже в задачах, где нет отсортированного массива, но есть возможность рассуждать про “хорошие” и “плохие” значения (или состояния).

Пример

Возьмём задачу: нужно найти последнее вхождение числа x = 7 в массиве nums = [2, 7, 7, 7, 7, 8, 9].

Разобьем все элементы на две группы:

Назовём элемент “хорошим”, если nums[i] <= 7
Назовём элемент “плохим”, если nums[i] > 7

Чтобы найти последнее вхождение 7, фактически мы ищем последний “хороший” элемент в массиве. Важно, чтобы сначала шли все хорошие, а потом все плохие. Если хорошие и плохие идут вразнобой, то применить бинарный поиск не получится.

Любая задача, где можно “разбить” массив (или последовательность) на “хорошие” и “плохие” элементы, решается бинарным поиском по этой границе. И даже если весь массив — это только “хорошие” или только “плохие” элементы, это тоже нормально.

Функция good - так в дальнейшем будем называть функцию, которая возвращает true, если элемент “хороший” и false в противном случае.

Поиск последнего элемента

Чтобы найти последнее вхождение target в отсортированном массиве, мы считаем элемент “хорошим”, если он <= target. Наша цель — найти последний такой “хороший” элемент.

export function search(nums, target) {
    let l = 0, r = nums.length;
    while (r - l > 1) {
        const m = Math.floor((l + r) / 2);
        if (nums[m] <= target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[l] === target ? l : -1;
}

class Solution
{
    public static int Search(int[] nums, int target)
    {
        int l = 0, r = nums.Length;
        while (r - l > 1)
        {
            int m = (l + r) / 2;
            if (nums[m] <= target)
            {
                l = m;
            }
            else
            {
                r = m;
            }
        }
        return nums[l] == target ? l : -1;
    }
}

#include <iostream>
#include <vector>

using namespace std;

int search(const vector<int>& nums, int target) {
    int l = 0, r = nums.size();
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (nums[m] <= target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[l] == target ? l : -1;
}

package main

func search(nums []int, target int) int {
    l, r := 0, len(nums)
    for r-l > 1 {
        m := (l + r) / 2
        if nums[m] <= target {
            l = m
        } else {
            r = m
        }
    }
    if nums[l] == target {
        return l
    }
    return -1
}

from typing import *

def search(nums: List[int], target: int) -> int:
    # Начало бинарного поиска
    # l = 0, а r = len(nums), потому что ответ в указателе l
    l, r = 0, len(nums)
    while r - l > 1:
        m = (l + r) // 2
        if nums[m] <= target: # Функция good
            l = m
        else:
            r = m    
    # Конец бинарного поиска
    return l if nums[l] == target else -1

export function search(nums, target) {
    let l = 0, r = nums.length;
    while (r - l > 1) {
        const m = Math.floor((l + r) / 2);
        if (nums[m] <= target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[l] === target ? l : -1;
}

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

Чтобы найти первое вхождение target, мы объявляем “хорошими” все элементы, которые < target. Тогда нам нужно найти первый “плохой” элемент, которым может оказаться и сам target. Для этого используем такой код:

class Solution
{
    public static int Search(int[] nums, int target)
    {
        int l = -1, r = nums.Length - 1;
        while (r - l > 1)
        {
            int m = (l + r) / 2;
            if (nums[m] < target)
            {
                l = m;
            }
            else
            {
                r = m;
            }
        }
        return nums[r] == target ? r : -1;
    }
}

#include <iostream>
#include <vector>

using namespace std;

int search(const vector<int>& nums, int target) {
    int l = -1, r = nums.size() - 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (nums[m] < target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[r] == target ? r : -1;
}

package main

func search(nums []int, target int) int {
    l, r := -1, len(nums)-1
    for r-l > 1 {
        m := (l + r) / 2
        if nums[m] < target {
            l = m
        } else {
            r = m
        }
    }
    if nums[r] == target {
        return r
    }
    return -1
}

public class Solution {
    public static int search(int[] nums, int target) {
        int l = -1, r = nums.length - 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (nums[m] < target) {
                l = m;
            } else {
                r = m;
            }
        }
        return nums[r] == target ? r : -1;
    }
}

from typing import *

def search(nums: List[int], target: int) -> int:
    # Начало бинарного поиска
    # l = -1, а r = len(nums) - 1, потому что ответ в указателе r
    l, r = -1, len(nums) - 1
    while r - l > 1:
        m = (l + r) // 2
        if nums[m] < target: # Функция good
            l = m
        else:
            r = m
    # Конец бинарного поиска
    return r if nums[r] == target else -1

export function search(nums, target) {
    let l = -1, r = nums.length - 1;
    while (r - l > 1) {
        const m = Math.floor((l + r) / 2);
        if (nums[m] < target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[r] === target ? r : -1;
}

Паттерн “бинарный поиск”

Видно, что обе реализации очень похожи. Можно выделить общий шаблон бинарного поиска, где меняются только две вещи:

Начальные значения l и r.
Функция good.

from typing import *

def search(nums: List[int], target: int) -> int:
    l, r = # Изменение 1: устанавливаем начальные значения
    while r - l > 1:
        m = (l + r) // 2
        if # Изменение 2: написать функцию good
            l = m
        else:
            r = m
    # Конец бинарного поиска
    return r if nums[r] == target else -1

class Solution
{
    public static int Search(int[] nums, int target)
    {
        int l = -1, r = nums.Length; // Изменение 1: устанавливаем начальные значения
        while (r - l > 1)
        {
            int m = (l + r) / 2;
            if (nums[m] < target) // Изменение 2: написать функцию good
            {
                l = m;
            }
            else
            {
                r = m;
            }
        }
        // Конец бинарного поиска
        if (r < nums.Length && nums[r] == target)
        {
            return r;
        }
        return -1;
    }
}

package main

func search(nums []int, target int) int {
    l, r := -1, len(nums) // Изменение 1: устанавливаем начальные значения
    for r-l > 1 {
        m := (l + r) / 2
        if nums[m] < target { // Изменение 2: написать функцию good
            l = m
        } else {
            r = m
        }
    }
    // Конец бинарного поиска
    if r < len(nums) && nums[r] == target {
        return r
    }
    return -1
}

public class Solution {
    public static int search(int[] nums, int target) {
        int l = -1, r = nums.length; // Изменение 1: устанавливаем начальные значения
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (nums[m] < target) { // Изменение 2: написать функцию good
                l = m;
            } else {
                r = m;
            }
        }
        // Конец бинарного поиска
        if (r < nums.length && nums[r] == target) {
            return r;
        }
        return -1;
    }
}

from typing import *

def search(nums: List[int], target: int) -> int:
    l, r = # Изменение 1: устанавливаем начальные значения
    while r - l > 1:
        m = (l + r) // 2
        if # Изменение 2: написать функцию good
            l = m
        else:
            r = m
    # Конец бинарного поиска
    return r if nums[r] == target else -1

export function search(nums, target) {
    let l = -1, r = nums.length; // Изменение 1: устанавливаем начальные значения
    while (r - l > 1) {
        const m = Math.floor((l + r) / 2);
        if (nums[m] < target) { // Изменение 2: написать функцию good
            l = m;
        } else {
            r = m;
        }
    }
    // Конец бинарного поиска
    if (r < nums.length && nums[r] === target) {
        return r;
    }
    return -1;
}

Во всех задачах про бинарный поиск тебе нужно правильно определить начальные границы l и r, а также функцию good (то есть логику, по которой ты решаешь, сдвигать l или r).

Типичные ошибки

Ошибка в функции good

Самая распространённая ошибка — пытаться в функции good использовать переменные l и r. Делать так нельзя, потому что:

l и r — это “служебные” указатели, которые мы меняем, чтобы найти ответ.
good должна определяться только на основе nums[m] (или самого m, если это другая постановка задачи). Так же там могут быть например nums[0] или например nums[m - 1], но только не переменные l и r.

Не используй указатели l и r в функции good!

Что дальше

Теперь, когда ты знаешь, как искать первое и последнее вхождение с помощью бинарного поиска и понимаешь идею “хороших” и “плохих” элементов, самое время перейти к практике. Попробуй решить несколько задач, применив эти шаблоны. Постарайся не подглядывать в готовый код, а самостоятельно прописать условие “good” и выбрать правильные начальные l и r.