12.2 Поисковая стратегия divide and conquer¶

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

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

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

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

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

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

По сути divide and conquer повышает эффективность поиска потому, что при полном переборе за один шаг удается исключить только один вариант, тогда как при поиске на основе divide and conquer за один шаг можно исключить половину вариантов.

1. Реализация двоичного поиска на основе divide and conquer¶

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

Question

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

С точки зрения divide and conquer обозначим подзадачу, соответствующую интервалу поиска \([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 показан процесс применения divide and conquer для поиска элемента \(6\) в массиве.

Процесс двоичного поиска в стиле divide and conquer

Рисунок 12-4 Процесс двоичного поиска в стиле divide and conquer

В реализации кода мы объявляем рекурсивную функцию 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 Поисковая стратегия divide and conquer¶

1. Реализация двоичного поиска на основе divide and conquer¶

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