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

# 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)\) , выполняем двоичный поиск по следующим шагам.

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

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

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

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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

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

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

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