Двоичный поиск – популярный алгоритм, используемый для эффективного поиска элемента в отсортированном массиве. Одним из важнейших шагов в реализации бинарного поиска является определение средней точки диапазона поиска. В этой статье блога мы рассмотрим различные методы поиска середины в двоичном поиске, а также примеры кода. Независимо от того, являетесь ли вы новичком или опытным программистом, это подробное руководство предоставит вам ряд возможностей для решения этой важной задачи.

Метод 1: базовый расчет
Самый простой способ найти среднее значение в двоичном поиске — вычислить его по формуле: среднее = (низкое + высокое) / 2. Вот пример фрагмента кода на Python:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Метод 2: побитовый сдвиг вправо
Другой эффективный способ найти середину — использовать операцию побитового сдвига вправо. Формула принимает вид: Mid = (низкий + высокий) >>1. Вот пример фрагмента кода на Java:

int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) >> 1;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

Метод 3: вычисление средней точки со смещением
В некоторых сценариях вычисление средней точки с использованием базовой формулы может привести к целочисленному переполнению, особенно при работе с большими массивами. Чтобы избежать этого, мы можем использовать подход, основанный на смещении. Вот пример фрагмента кода на C++:

int binarySearch(vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    while (low <= high) {
        int offset = low + (high - low) / 2;
        int mid = low + offset;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}