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

# 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\) .

<1><2><3><4><5><6><7>

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

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

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

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

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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\) линейный поиск может оказаться быстрее двоичного.

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