Перейти к содержанию

10.1   Двоичный поиск

Двоичный поиск (binary search) - это эффективный алгоритм поиска, основанный на стратегии «разделяй и властвуй». Он использует упорядоченность данных, сокращая на каждом шаге область поиска вдвое, пока не будет найден целевой элемент или пока интервал поиска не опустеет.

Question

Дан массив nums длины \(n\), элементы которого расположены в порядке возрастания и не повторяются. Найдите и верните индекс элемента target в этом массиве. Если массив не содержит этого элемента, верните \(-1\) . Пример показан на рисунке 10-1.

Пример данных для двоичного поиска

Рисунок 10-1   Пример данных для двоичного поиска

Как показано на рисунке 10-2, сначала инициализируем указатели \(i = 0\) и \(j = n - 1\) , которые указывают на первый и последний элементы массива и задают интервал поиска \([0, n - 1]\) . Обратите внимание: квадратные скобки обозначают замкнутый интервал и включают граничные значения.

Далее в цикле выполняются следующие два шага.

  1. Вычислить индекс середины \(m = \lfloor {(i + j) / 2} \rfloor\) , где \(\lfloor \: \rfloor\) означает операцию округления вниз.
  2. Сравнить nums[m] и target , после чего возможны три случая.
    1. Если nums[m] < target , это означает, что target находится в интервале \([m + 1, j]\) , поэтому выполняется \(i = m + 1\) .
    2. Если nums[m] > target , это означает, что target находится в интервале \([i, m - 1]\) , поэтому выполняется \(j = m - 1\) .
    3. Если nums[m] = target , значит, элемент target найден, поэтому возвращается индекс \(m\) .

Если массив не содержит целевой элемент, область поиска в итоге сузится до пустого интервала. В этом случае возвращается \(-1\) .

Процесс двоичного поиска

binary_search_step2

binary_search_step3

binary_search_step4

binary_search_step5

binary_search_step6

binary_search_step7

Рисунок 10-2   Процесс двоичного поиска

Стоит отметить, что поскольку и \(i\) , и \(j\) имеют тип int , то сумма \(i + j\) может выйти за пределы диапазона типа int. Чтобы избежать переполнения, обычно используют формулу \(m = \lfloor {i + (j - i) / 2} \rfloor\) для вычисления середины.

Код приведен ниже:

binary_search.py
def binary_search(nums: list[int], target: int) -> int:
    """Бинарный поиск (двусторонне замкнутый интервал)"""
    # Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    i, j = 0, len(nums) - 1
    # Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while i <= j:
        # Теоретически числа в Python могут быть сколь угодно большими (ограничены только объемом памяти), поэтому не нужно учитывать переполнение больших чисел
        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  # Целевой элемент найден, вернуть его индекс
    return -1  # Целевой элемент не найден, вернуть -1
binary_search.cpp
/* Бинарный поиск (двусторонне замкнутый интервал) */
int binarySearch(vector<int> &nums, int target) {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    int i = 0, j = nums.size() - 1;
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while (i <= j) {
        int m = i + (j - i) / 2; // Вычислить индекс середины m
        if (nums[m] < target)    // Это означает, что target находится в интервале [m+1, j]
            i = m + 1;
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m-1]
            j = m - 1;
        else // Целевой элемент найден, вернуть его индекс
            return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.java
/* Бинарный поиск (двусторонне замкнутый интервал) */
int binarySearch(int[] nums, int target) {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    int i = 0, j = nums.length - 1;
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while (i <= j) {
        int m = i + (j - i) / 2; // Вычислить индекс середины m
        if (nums[m] < target) // Это означает, что target находится в интервале [m+1, j]
            i = m + 1;
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m-1]
            j = m - 1;
        else // Целевой элемент найден, вернуть его индекс
            return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.cs
/* Бинарный поиск (двусторонне замкнутый интервал) */
int BinarySearch(int[] nums, int target) {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    int i = 0, j = nums.Length - 1;
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while (i <= j) {
        int m = i + (j - i) / 2;   // Вычислить индекс середины m
        if (nums[m] < target)      // Это означает, что target находится в интервале [m+1, j]
            i = m + 1;
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m-1]
            j = m - 1;
        else                       // Целевой элемент найден, вернуть его индекс
            return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.go
/* Бинарный поиск (двусторонне замкнутый интервал) */
func binarySearch(nums []int, target int) int {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    i, j := 0, len(nums)-1
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    for i <= j {
        m := i + (j-i)/2      // Вычислить индекс середины m
        if nums[m] < target { // Это означает, что target находится в интервале [m+1, j]
            i = m + 1
        } else if nums[m] > target { // Это означает, что target находится в интервале [i, m-1]
            j = m - 1
        } else { // Целевой элемент найден, вернуть его индекс
            return m
        }
    }
    // Целевой элемент не найден, вернуть -1
    return -1
}
binary_search.swift
/* Бинарный поиск (двусторонне замкнутый интервал) */
func binarySearch(nums: [Int], target: Int) -> Int {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    var i = nums.startIndex
    var j = nums.endIndex - 1
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while i <= j {
        let m = i + (j - i) / 2 // Вычислить индекс середины m
        if nums[m] < target { // Это означает, что target находится в интервале [m+1, j]
            i = m + 1
        } else if nums[m] > target { // Это означает, что target находится в интервале [i, m-1]
            j = m - 1
        } else { // Целевой элемент найден, вернуть его индекс
            return m
        }
    }
    // Целевой элемент не найден, вернуть -1
    return -1
}
binary_search.js
/* Бинарный поиск (двусторонне замкнутый интервал) */
function binarySearch(nums, target) {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    let i = 0,
        j = nums.length - 1;
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while (i <= j) {
        // Вычислить индекс середины m, используя parseInt() для округления вниз
        const m = parseInt(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 return m; // Целевой элемент найден, вернуть его индекс
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.ts
/* Бинарный поиск (двусторонне замкнутый интервал) */
function binarySearch(nums: number[], target: number): number {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    let i = 0,
        j = nums.length - 1;
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while (i <= j) {
        // Вычислить индекс середины m
        const m = Math.floor(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 {
            // Целевой элемент найден, вернуть его индекс
            return m;
        }
    }
    return -1; // Целевой элемент не найден, вернуть -1
}
binary_search.dart
/* Бинарный поиск (двусторонне замкнутый интервал) */
int binarySearch(List<int> nums, int target) {
  // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
  int i = 0, j = nums.length - 1;
  // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
  while (i <= j) {
    int m = i + (j - i) ~/ 2; // Вычислить индекс середины m
    if (nums[m] < target) {
      // Это означает, что target находится в интервале [m+1, j]
      i = m + 1;
    } else if (nums[m] > target) {
      // Это означает, что target находится в интервале [i, m-1]
      j = m - 1;
    } else {
      // Целевой элемент найден, вернуть его индекс
      return m;
    }
  }
  // Целевой элемент не найден, вернуть -1
  return -1;
}
binary_search.rs
/* Бинарный поиск (двусторонне замкнутый интервал) */
fn binary_search(nums: &[i32], target: i32) -> i32 {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    let mut i = 0;
    let mut j = nums.len() as i32 - 1;
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while i <= j {
        let m = i + (j - i) / 2; // Вычислить индекс середины m
        if nums[m as usize] < target {
            // Это означает, что target находится в интервале [m+1, j]
            i = m + 1;
        } else if nums[m as usize] > target {
            // Это означает, что target находится в интервале [i, m-1]
            j = m - 1;
        } else {
            // Целевой элемент найден, вернуть его индекс
            return m;
        }
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.c
/* Бинарный поиск (двусторонне замкнутый интервал) */
int binarySearch(int *nums, int len, int target) {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    int i = 0, j = len - 1;
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while (i <= j) {
        int m = i + (j - i) / 2; // Вычислить индекс середины m
        if (nums[m] < target)    // Это означает, что target находится в интервале [m+1, j]
            i = m + 1;
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m-1]
            j = m - 1;
        else // Целевой элемент найден, вернуть его индекс
            return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.kt
/* Бинарный поиск (двусторонне замкнутый интервал) */
fun binarySearch(nums: IntArray, target: Int): Int {
    // Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
    var i = 0
    var j = nums.size - 1
    // Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
    while (i <= j) {
        val m = i + (j - i) / 2 // Вычислить индекс середины m
        if (nums[m] < target) // Это означает, что target находится в интервале [m+1, j]
            i = m + 1
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m-1]
            j = m - 1
        else  // Целевой элемент найден, вернуть его индекс
            return m
    }
    // Целевой элемент не найден, вернуть -1
    return -1
}
binary_search.rb
### Бинарный поиск (двусторонне замкнутый интервал) ###
def binary_search(nums, target)
  # Инициализировать двусторонне замкнутый интервал [0, n-1], то есть i и j указывают на первый и последний элементы массива соответственно
  i, j = 0, nums.length - 1

  # Цикл завершается, когда диапазон поиска пуст (при i > j диапазон пуст)
  while i <= j
    # Теоретически числа в Ruby могут быть сколь угодно большими (ограничены только объемом памяти), поэтому не нужно учитывать переполнение больших чисел
    m = (i + j) / 2   # Вычислить индекс середины m

    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  # Целевой элемент найден, вернуть его индекс
    end
  end

  -1  # Целевой элемент не найден, вернуть -1
end
Визуализация кода

Временная сложность равна \(O(\log n)\) : в цикле двоичного поиска интервал каждый раз сокращается вдвое, поэтому число итераций равно \(\log_2 n\) .

Пространственная сложность равна \(O(1)\) : указатели \(i\) и \(j\) занимают константный объем памяти.

10.1.1   Методы представления интервалов

Помимо описанного выше двойного замкнутого интервала, часто используется и левозамкнутый правооткрытый интервал, который задается как \([0, n)\) , то есть левая граница включается, а правая - нет. В этом представлении интервал \([i, j)\) пуст, когда \(i = j\) .

На основе этого представления можно реализовать двоичный поиск с той же функциональностью:

binary_search.py
def binary_search_lcro(nums: list[int], target: int) -> int:
    """Бинарный поиск (лево замкнутый, право открытый интервал)"""
    # Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    i, j = 0, len(nums)
    # Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    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  # Это означает, что target находится в интервале [i, m)
        else:
            return m  # Целевой элемент найден, вернуть его индекс
    return -1  # Целевой элемент не найден, вернуть -1
binary_search.cpp
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
int binarySearchLCRO(vector<int> &nums, int target) {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    int i = 0, j = nums.size();
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while (i < j) {
        int m = i + (j - i) / 2; // Вычислить индекс середины m
        if (nums[m] < target)    // Это означает, что target находится в интервале [m+1, j)
            i = m + 1;
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m)
            j = m;
        else // Целевой элемент найден, вернуть его индекс
            return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.java
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
int binarySearchLCRO(int[] nums, int target) {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    int i = 0, j = nums.length;
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while (i < j) {
        int m = i + (j - i) / 2; // Вычислить индекс середины m
        if (nums[m] < target) // Это означает, что target находится в интервале [m+1, j)
            i = m + 1;
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m)
            j = m;
        else // Целевой элемент найден, вернуть его индекс
            return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.cs
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
int BinarySearchLCRO(int[] nums, int target) {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    int i = 0, j = nums.Length;
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while (i < j) {
        int m = i + (j - i) / 2;   // Вычислить индекс середины m
        if (nums[m] < target)      // Это означает, что target находится в интервале [m+1, j)
            i = m + 1;
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m)
            j = m;
        else                       // Целевой элемент найден, вернуть его индекс
            return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.go
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
func binarySearchLCRO(nums []int, target int) int {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    i, j := 0, len(nums)
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    for i < j {
        m := i + (j-i)/2      // Вычислить индекс середины m
        if nums[m] < target { // Это означает, что target находится в интервале [m+1, j)
            i = m + 1
        } else if nums[m] > target { // Это означает, что target находится в интервале [i, m)
            j = m
        } else { // Целевой элемент найден, вернуть его индекс
            return m
        }
    }
    // Целевой элемент не найден, вернуть -1
    return -1
}
binary_search.swift
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
func binarySearchLCRO(nums: [Int], target: Int) -> Int {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    var i = nums.startIndex
    var j = nums.endIndex
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while i < j {
        let m = i + (j - i) / 2 // Вычислить индекс середины m
        if nums[m] < target { // Это означает, что target находится в интервале [m+1, j)
            i = m + 1
        } else if nums[m] > target { // Это означает, что target находится в интервале [i, m)
            j = m
        } else { // Целевой элемент найден, вернуть его индекс
            return m
        }
    }
    // Целевой элемент не найден, вернуть -1
    return -1
}
binary_search.js
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
function binarySearchLCRO(nums, target) {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    let i = 0,
        j = nums.length;
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while (i < j) {
        // Вычислить индекс середины m, используя parseInt() для округления вниз
        const m = parseInt(i + (j - i) / 2);
        if (nums[m] < target)
            // Это означает, что target находится в интервале [m+1, j)
            i = m + 1;
        else if (nums[m] > target)
            // Это означает, что target находится в интервале [i, m)
            j = m;
        // Целевой элемент найден, вернуть его индекс
        else return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.ts
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
function binarySearchLCRO(nums: number[], target: number): number {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    let i = 0,
        j = nums.length;
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while (i < j) {
        // Вычислить индекс середины m
        const m = Math.floor(i + (j - i) / 2);
        if (nums[m] < target) {
            // Это означает, что target находится в интервале [m+1, j)
            i = m + 1;
        } else if (nums[m] > target) {
            // Это означает, что target находится в интервале [i, m)
            j = m;
        } else {
            // Целевой элемент найден, вернуть его индекс
            return m;
        }
    }
    return -1; // Целевой элемент не найден, вернуть -1
}
binary_search.dart
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
int binarySearchLCRO(List<int> nums, int target) {
  // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
  int i = 0, j = nums.length;
  // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
  while (i < j) {
    int m = i + (j - i) ~/ 2; // Вычислить индекс середины m
    if (nums[m] < target) {
      // Это означает, что target находится в интервале [m+1, j)
      i = m + 1;
    } else if (nums[m] > target) {
      // Это означает, что target находится в интервале [i, m)
      j = m;
    } else {
      // Целевой элемент найден, вернуть его индекс
      return m;
    }
  }
  // Целевой элемент не найден, вернуть -1
  return -1;
}
binary_search.rs
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
fn binary_search_lcro(nums: &[i32], target: i32) -> i32 {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    let mut i = 0;
    let mut j = nums.len() as i32;
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while i < j {
        let m = i + (j - i) / 2; // Вычислить индекс середины m
        if nums[m as usize] < target {
            // Это означает, что target находится в интервале [m+1, j)
            i = m + 1;
        } else if nums[m as usize] > target {
            // Это означает, что target находится в интервале [i, m)
            j = m;
        } else {
            // Целевой элемент найден, вернуть его индекс
            return m;
        }
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.c
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
int binarySearchLCRO(int *nums, int len, int target) {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    int i = 0, j = len;
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while (i < j) {
        int m = i + (j - i) / 2; // Вычислить индекс середины m
        if (nums[m] < target)    // Это означает, что target находится в интервале [m+1, j)
            i = m + 1;
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m)
            j = m;
        else // Целевой элемент найден, вернуть его индекс
            return m;
    }
    // Целевой элемент не найден, вернуть -1
    return -1;
}
binary_search.kt
/* Бинарный поиск (лево замкнутый, право открытый интервал) */
fun binarySearchLCRO(nums: IntArray, target: Int): Int {
    // Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
    var i = 0
    var j = nums.size
    // Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
    while (i < j) {
        val m = i + (j - i) / 2 // Вычислить индекс середины m
        if (nums[m] < target) // Это означает, что target находится в интервале [m+1, j)
            i = m + 1
        else if (nums[m] > target) // Это означает, что target находится в интервале [i, m)
            j = m
        else  // Целевой элемент найден, вернуть его индекс
            return m
    }
    // Целевой элемент не найден, вернуть -1
    return -1
}
binary_search.rb
### Бинарный поиск (лево замкнутый, право открытый интервал) ###
def binary_search_lcro(nums, target)
  # Инициализировать лево замкнутый, право открытый интервал [0, n), то есть i и j указывают на первый элемент массива и позицию сразу за последним элементом соответственно
  i, j = 0, nums.length

  # Цикл завершается, когда диапазон поиска пуст (при i = j диапазон пуст)
  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)
    else
      return m  # Целевой элемент найден, вернуть его индекс
    end
  end

  -1  # Целевой элемент не найден, вернуть -1
end
Визуализация кода

Как показано на рисунке 10-3, в этих двух вариантах представления интервала различаются инициализация, условие цикла и операция сужения интервала в алгоритме двоичного поиска.

Поскольку в записи «двойной замкнутый интервал» обе границы являются закрытыми, операции сужения интервала при помощи указателей \(i\) и \(j\) тоже получаются симметричными. Из-за этого в таком варианте сложнее допустить ошибку, поэтому обычно рекомендуется использовать именно запись «двойной замкнутый интервал».

Два определения интервалов

Рисунок 10-3   Два определения интервалов

10.1.2   Преимущества и ограничения

Двоичный поиск показывает хорошие результаты и по времени, и по памяти.

  • Двоичный поиск очень эффективен по времени. На больших объемах данных логарифмическая временная сложность дает заметное преимущество. Например, когда размер данных \(n = 2^{20}\) , линейный поиск потребует \(2^{20} = 1048576\) итераций, тогда как двоичный поиск выполнится всего за \(\log_2 2^{20} = 20\) итераций.
  • Двоичный поиск не требует дополнительной памяти. По сравнению с алгоритмами поиска, которым нужно внешнее пространство (например, с хеш-поиском), двоичный поиск заметно экономнее по памяти.

Однако двоичный поиск подходит не для всех ситуаций, и основные причины таковы.

  • Двоичный поиск применим только к упорядоченным данным. Если входные данные неупорядочены, специально сортировать их ради двоичного поиска невыгодно. Это связано с тем, что временная сложность алгоритмов сортировки обычно составляет \(O(n \log n)\) , что выше, чем у линейного и двоичного поиска. Если элементы приходится часто вставлять, то для сохранения порядка в массиве их нужно помещать в конкретные позиции, а это требует \(O(n)\) времени и тоже обходится дорого.
  • Двоичный поиск применим только к массивам. Для него нужен скачкообразный доступ к элементам, а в связном списке такой доступ малоэффективен, поэтому двоичный поиск не подходит для списков и структур данных, построенных на их основе.
  • При малом объеме данных линейный поиск работает лучше. В линейном поиске на каждом шаге нужна всего одна операция сравнения. В двоичном поиске требуется 1 сложение, 1 деление, от 1 до 3 сравнений и еще 1 сложение или вычитание, то есть всего от 4 до 6 элементарных операций. Поэтому при небольшом \(n\) линейный поиск может оказаться быстрее двоичного.
Оставляйте свои идеи, вопросы и предложения в комментариях