Binary Search C: алгоритм бинарного поиска на языке C

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

Для реализации бинарного поиска на языке C используется рекурсивный или итеративный подход. Рассмотрим рекурсивную реализацию.

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int x) {
    if (high >= low) { // проверяем, что остался хотя бы один элемент для поиска
        int mid = low + (high - low) / 2; // находим индекс среднего элемента массива

        if (arr[mid] == x) {
            return mid; // искомый элемент найден, возвращаем его индекс
        } else if (arr[mid] > x) {
            return binarySearch(arr, low, mid - 1, x); // искомый элемент находится в левой половине массива
        } else {
            return binarySearch(arr, mid + 1, high, x); // искомый элемент находится в правой половине массива
        }
    }
  
    return -1; // искомый элемент не найден
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int n = sizeof(arr) / sizeof(arr[0]); // вычисляем размер массива
    int x = 10; // искомый элемент для поиска
    int result = binarySearch(arr, 0, n - 1, x); // вызываем функцию бинарного поиска

    if (result == -1) {
        printf("Элемент не найден");
    } else {
        printf("Элемент найден на позиции %d", result);
    }

    return 0;
}

В данном примере мы имеем отсортированный массив arr, содержащий числа от 2 до 20 с шагом 2. Здесь мы хотим найти элемент со значением 10. Сначала мы вычисляем размер массива n с помощью выражения sizeof(arr) / sizeof(arr[0]), чтобы передать его в функцию binarySearch. Затем вызываем функцию бинарного поиска и присваиваем результат переменной result. После этого проверяем результат: если он равен -1, выводим сообщение "Элемент не найден", иначе выводим сообщение с позицией найденного элемента.

Выполняя код, получим вывод: "Элемент найден на позиции 4".

Использование бинарного поиска вместо простого последовательного поиска позволяет существенно ускорить поиск в больших массивах данных. Этот алгоритм имеет сложность O(log n), что делает его пригодным для работы с большими объемами информации. Однако для его применения массив должен быть предварительно отсортирован по возрастанию или убыванию.

Надеюсь, данный ответ был полезен. Если у вас возникнут еще вопросы, не стесняйтесь задавать!