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

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\) линейный поиск может оказаться быстрее двоичного.
Оставляйте свои идеи, вопросы и предложения в комментариях