12.2 Поисковая стратегия разделяй и властвуй¶

Мы уже знаем, что алгоритмы поиска делятся на две большие категории.

Полный перебор: реализуется через обход структуры данных, временная сложность равна \(O(n)\) .
Адаптивный поиск: использует особую организацию данных или априорную информацию, временная сложность может достигать \(O(\log n)\) и даже \(O(1)\) .

На практике алгоритмы поиска с временной сложностью \(O(\log n)\) обычно реализуются на основе стратегии «разделяй и властвуй», например двоичный поиск и деревья.

На каждом шаге двоичный поиск раскладывает задачу (поиск целевого элемента в массиве) на более мелкую задачу (поиск целевого элемента в одной половине массива), и этот процесс продолжается, пока массив не станет пустым или пока не будет найден целевой элемент.
Деревья являются типичными представителями идей «разделяй и властвуй». В таких структурах данных, как двоичное дерево поиска, AVL-дерево и куча, временная сложность различных операций равна \(O(\log n)\) .

Стратегия «разделяй и властвуй» для двоичного поиска выглядит следующим образом.

Задача раскладывается на части: двоичный поиск рекурсивно разбивает исходную задачу (поиск в массиве) на подзадачу (поиск в одной половине массива), и это достигается сравнением среднего элемента с целевым значением.
Подзадачи независимы: в двоичном поиске на каждом шаге обрабатывается только одна подзадача, и она не зависит от других подзадач.
Решения подзадач не нужно объединять: двоичный поиск нацелен на поиск конкретного элемента, поэтому объединять решения подзадач не требуется. Как только подзадача решена, одновременно считается решенной и исходная задача.

Иными словами, стратегия «разделяй и властвуй» повышает эффективность поиска потому, что при полном переборе за один шаг удается исключить только один вариант, тогда как при поиске на основе «разделяй и властвуй» за один шаг можно исключить половину вариантов.

1. Реализация двоичного поиска на основе «разделяй и властвуй»¶

В предыдущих главах двоичный поиск реализовывался через итерацию. Теперь реализуем его с помощью стратегии «разделяй и властвуй», то есть через рекурсию.

Question

Дан отсортированный массив nums длины \(n\) , в котором все элементы уникальны. Найдите элемент target .

С точки зрения стратегии «разделяй и властвуй» обозначим подзадачу, соответствующую интервалу поиска \([i, j]\) , через \(f(i, j)\) .

Начиная с исходной задачи \(f(0, n-1)\) , выполняем двоичный поиск по следующим шагам.

Вычислить середину \(m\) интервала поиска \([i, j]\) и с ее помощью исключить половину интервала.
Рекурсивно решить подзадачу вдвое меньшего размера. Это может быть либо \(f(i, m-1)\) , либо \(f(m+1, j)\) .
Повторять шаг 1. и шаг 2. , пока не будет найден target или пока интервал не станет пустым.

На рисунке 12-4 показан процесс применения стратегии «разделяй и властвуй» для поиска элемента \(6\) в массиве.

Процесс двоичного поиска в стиле разделяй и властвуй

Рисунок 12-4 Процесс двоичного поиска в стиле разделяй и властвуй

В реализации кода мы объявляем рекурсивную функцию dfs() для решения задачи \(f(i, j)\) :

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search_recur.py

def dfs(nums: list[int], target: int, i: int, j: int) -> int:
    """Бинарный поиск: задача f(i, j)"""
    # Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if i > j:
        return -1
    # Вычислить индекс середины m
    m = (i + j) // 2
    if nums[m] < target:
        # Рекурсивная подзадача f(m+1, j)
        return dfs(nums, target, m + 1, j)
    elif nums[m] > target:
        # Рекурсивная подзадача f(i, m-1)
        return dfs(nums, target, i, m - 1)
    else:
        # Целевой элемент найден, вернуть его индекс
        return m

def binary_search(nums: list[int], target: int) -> int:
    """Бинарный поиск"""
    n = len(nums)
    # Решить задачу f(0, n-1)
    return dfs(nums, target, 0, n - 1)

binary_search_recur.cpp

/* Бинарный поиск: задача f(i, j) */
int dfs(vector<int> &nums, int target, int i, int j) {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if (i > j) {
        return -1;
    }
    // Вычислить индекс середины m
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // Рекурсивная подзадача f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // Рекурсивная подзадача f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m;
    }
}

/* Бинарный поиск */
int binarySearch(vector<int> &nums, int target) {
    int n = nums.size();
    // Решить задачу f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.java

/* Бинарный поиск: задача f(i, j) */
int dfs(int[] nums, int target, int i, int j) {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if (i > j) {
        return -1;
    }
    // Вычислить индекс середины m
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // Рекурсивная подзадача f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // Рекурсивная подзадача f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m;
    }
}

/* Бинарный поиск */
int binarySearch(int[] nums, int target) {
    int n = nums.length;
    // Решить задачу f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.cs

/* Бинарный поиск: задача f(i, j) */
int DFS(int[] nums, int target, int i, int j) {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if (i > j) {
        return -1;
    }
    // Вычислить индекс середины m
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // Рекурсивная подзадача f(m+1, j)
        return DFS(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // Рекурсивная подзадача f(i, m-1)
        return DFS(nums, target, i, m - 1);
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m;
    }
}

/* Бинарный поиск */
int BinarySearch(int[] nums, int target) {
    int n = nums.Length;
    // Решить задачу f(0, n-1)
    return DFS(nums, target, 0, n - 1);
}

binary_search_recur.go

/* Бинарный поиск: задача f(i, j) */
func dfs(nums []int, target, i, j int) int {
    // Если интервал пуст, это означает отсутствие целевого элемента, вернуть -1
    if i > j {
        return -1
    }
    // Вычислить средний индекс
    m := i + ((j - i) >> 1)
    // Сравнить середину и целевой элемент
    if nums[m] < target {
        // Если меньше, рекурсивно обрабатывать правую половину массива
        // Рекурсивная подзадача f(m+1, j)
        return dfs(nums, target, m+1, j)
    } else if nums[m] > target {
        // Если больше, рекурсивно обработать левую половину массива
        // Рекурсивная подзадача f(i, m-1)
        return dfs(nums, target, i, m-1)
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m
    }
}

/* Бинарный поиск */
func binarySearch(nums []int, target int) int {
    n := len(nums)
    return dfs(nums, target, 0, n-1)
}

binary_search_recur.swift

/* Бинарный поиск: задача f(i, j) */
func dfs(nums: [Int], target: Int, i: Int, j: Int) -> Int {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if i > j {
        return -1
    }
    // Вычислить индекс середины m
    let m = (i + j) / 2
    if nums[m] < target {
        // Рекурсивная подзадача f(m+1, j)
        return dfs(nums: nums, target: target, i: m + 1, j: j)
    } else if nums[m] > target {
        // Рекурсивная подзадача f(i, m-1)
        return dfs(nums: nums, target: target, i: i, j: m - 1)
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m
    }
}

/* Бинарный поиск */
func binarySearch(nums: [Int], target: Int) -> Int {
    // Решить задачу f(0, n-1)
    dfs(nums: nums, target: target, i: nums.startIndex, j: nums.endIndex - 1)
}

binary_search_recur.js

/* Бинарный поиск: задача f(i, j) */
function dfs(nums, target, i, j) {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if (i > j) {
        return -1;
    }
    // Вычислить индекс середины m
    const m = i + ((j - i) >> 1);
    if (nums[m] < target) {
        // Рекурсивная подзадача f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // Рекурсивная подзадача f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m;
    }
}

/* Бинарный поиск */
function binarySearch(nums, target) {
    const n = nums.length;
    // Решить задачу f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.ts

/* Бинарный поиск: задача f(i, j) */
function dfs(nums: number[], target: number, i: number, j: number): number {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if (i > j) {
        return -1;
    }
    // Вычислить индекс середины m
    const m = i + ((j - i) >> 1);
    if (nums[m] < target) {
        // Рекурсивная подзадача f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // Рекурсивная подзадача f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m;
    }
}

/* Бинарный поиск */
function binarySearch(nums: number[], target: number): number {
    const n = nums.length;
    // Решить задачу f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.dart

/* Бинарный поиск: задача f(i, j) */
int dfs(List<int> nums, int target, int i, int j) {
  // Если интервал пуст, целевой элемент отсутствует, вернуть -1
  if (i > j) {
    return -1;
  }
  // Вычислить индекс середины m
  int m = (i + j) ~/ 2;
  if (nums[m] < target) {
    // Рекурсивная подзадача f(m+1, j)
    return dfs(nums, target, m + 1, j);
  } else if (nums[m] > target) {
    // Рекурсивная подзадача f(i, m-1)
    return dfs(nums, target, i, m - 1);
  } else {
    // Целевой элемент найден, вернуть его индекс
    return m;
  }
}

/* Бинарный поиск */
int binarySearch(List<int> nums, int target) {
  int n = nums.length;
  // Решить задачу f(0, n-1)
  return dfs(nums, target, 0, n - 1);
}

binary_search_recur.rs

/* Бинарный поиск: задача f(i, j) */
fn dfs(nums: &[i32], target: i32, i: i32, j: i32) -> i32 {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if i > j {
        return -1;
    }
    let m: i32 = i + (j - i) / 2;
    if nums[m as usize] < target {
        // Рекурсивная подзадача f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if nums[m as usize] > target {
        // Рекурсивная подзадача f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m;
    }
}

/* Бинарный поиск */
fn binary_search(nums: &[i32], target: i32) -> i32 {
    let n = nums.len() as i32;
    // Решить задачу f(0, n-1)
    dfs(nums, target, 0, n - 1)
}

binary_search_recur.c

/* Бинарный поиск: задача f(i, j) */
int dfs(int nums[], int target, int i, int j) {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if (i > j) {
        return -1;
    }
    // Вычислить индекс середины m
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // Рекурсивная подзадача f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // Рекурсивная подзадача f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // Целевой элемент найден, вернуть его индекс
        return m;
    }
}

/* Бинарный поиск */
int binarySearch(int nums[], int target, int numsSize) {
    int n = numsSize;
    // Решить задачу f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}

binary_search_recur.kt

/* Бинарный поиск: задача f(i, j) */
fun dfs(
    nums: IntArray,
    target: Int,
    i: Int,
    j: Int
): Int {
    // Если интервал пуст, целевой элемент отсутствует, вернуть -1
    if (i > j) {
        return -1
    }
    // Вычислить индекс середины m
    val m = (i + j) / 2
    return if (nums[m] < target) {
        // Рекурсивная подзадача f(m+1, j)
        dfs(nums, target, m + 1, j)
    } else if (nums[m] > target) {
        // Рекурсивная подзадача f(i, m-1)
        dfs(nums, target, i, m - 1)
    } else {
        // Целевой элемент найден, вернуть его индекс
        m
    }
}

/* Бинарный поиск */
fun binarySearch(nums: IntArray, target: Int): Int {
    val n = nums.size
    // Решить задачу f(0, n-1)
    return dfs(nums, target, 0, n - 1)
}

binary_search_recur.rb

### Бинарный поиск: задача f(i, j) ###
def dfs(nums, target, i, j)
  # Если интервал пуст, целевой элемент отсутствует, вернуть -1
  return -1 if i > j

  # Вычислить индекс середины m
  m = (i + j) / 2

  if nums[m] < target
    # Рекурсивная подзадача f(m+1, j)
    return dfs(nums, target, m + 1, j)
  elsif nums[m] > target
    # Рекурсивная подзадача f(i, m-1)
    return dfs(nums, target, i, m - 1)
  else
    # Целевой элемент найден, вернуть его индекс
    return m
  end
end

### Бинарный поиск ###
def binary_search(nums, target)
  n = nums.length
  # Решить задачу f(0, n-1)
  dfs(nums, target, 0, n - 1)
end

Визуализация кода

Во весь экран >

12.2 Поисковая стратегия разделяй и властвуй¶

1. Реализация двоичного поиска на основе «разделяй и властвуй»¶

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