Бинарный поиск в C

Бинарный поиск - это упрощенный алгоритм, предназначенный для определения местоположения элемента, хранящегося в отсортированном списке. В программе на языке Си существует несколько вариантов бинарного поиска, таких как проверка на равенство и "меньше, чем" на каждом шаге алгоритма.

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

Прежде чем предоставить вам код для запуска бинарного поиска на C, давайте сначала разберемся, как именно работает этот алгоритм.

Как это работает?

Алгоритм бинарного поиска применяется к отсортированному массиву для поиска элемента. Поиск начинается со сравнения целевого элемента со средним элементом массива. Если значение совпадает, то возвращается позиция элемента.

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

Процесс аналогичен, когда целевой элемент больше среднего, только в этом случае первая половина массива отбрасывается, прежде чем продолжить поиск. Итерация повторяется до тех пор, пока не будет найдено совпадение с целевым элементом.

Бинарный поиск в программе на языке Си

Следующий код реализует двоичный поиск на языке программирования Си. Хотя его можно использовать только для отсортированных массивов, он быстр по сравнению с линейным поиском.

Если требования требуют использования двоичного поиска в несортированном массиве, то его необходимо сначала отсортировать, прежде чем использовать алгоритм двоичного поиска. Для этого вы можете использовать некоторые методы сортировки, такие как пузырьковая сортировка или сортировка слиянием.

ПРИМЕЧАНИЕ: - Приведенный ниже код предполагает, что введенные номера следуют в порядке возрастания!

Вот код для бинарного поиска на C:

#include 
int main()
{
   int c, first, last, middle, n, search, array[100];
   printf("Enter number of elements:\n");
   scanf("%d",&n); 
   printf("Enter %d integers:\n", n);
   for (c = 0; c < n; c++)
      scanf("%d",&array[c]); 
   printf("Enter the value to find:\n");
   scanf("%d", &search);
   first = 0;
   last = n - 1;
   middle = (first+last)/2;
   while (first <= last) {
      if (array[middle] < search)
         first = middle + 1;    
      else if (array[middle] == search) {
         printf("%d is present at index %d.\n", search, middle+1);
         break;
      }
      else
         last = middle - 1;
      middle = (first + last)/2;
   }
   if (first > last)
      printf("Not found! %d is not present in the list.\n", search);
   return 0;  
}

Примерный результат:

Введите количество элементов:

5

Введите 5 целых чисел:

19222446

Введите значение, которое требуется найти:

24

24 присутствует в индексе 4.

Другие примеры реализации бинарного поиска в программе на языке Си

• Рекурсивная реализация бинарного поиска

ПРИМЕЧАНИЕ: - Эта программа не позволяет вам вводить элементы, поскольку в ней уже реализован список. Программа просто демонстрирует, как работает бинарный поиск в программе на C!

#include 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
        if (arr[mid] == x) 
            return mid; 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
        return binarySearch(arr, mid + 1, r, x); 
    } 
    return -1; 
}  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 10; 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? printf("The element is not present in array") 
                   : printf("The element is present at index %d", 
                            result); 
    return 0; 
}

Выход:

Элемент присутствует по индексу 3.

• Итеративная реализация бинарного поиска

ПРИМЕЧАНИЕ: - Эта программа не позволяет вам вводить элементы, поскольку в ней уже реализован список. Программа просто демонстрирует, как работает бинарный поиск в программе на C!

#include 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
        if (arr[m] == x) 
            return m; 
        if (arr[m] < x) 
            l = m + 1; 
        else
            r = m - 1; 
    }  
    return -1; 
}   
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 10; 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? printf("The element is not present"
                            " in array") 
                   : printf("The element is present at "
                            "index %d", 
                            result); 
    return 0; 
} 

Выход:

Элемент присутствует по индексу 3.

Рекомендуемый курс

От 

Временные сложности алгоритма бинарного поиска

Предположим, что T(N) - это временная сложность бинарного поиска набора из N элементов. Затем,

T(N) = T(N/2) + O(1) (с помощью рекуррентного соотношения) - (i)

Теперь, применяя теорему Мастерса для вычисления сложности рекуррентных соотношений во время выполнения, т.е.

T(N) = aT(N/b) + f(N) - (ii)

Сравнивая уравнение (ii) с (i), получаем,

a = 1, b = 2

Следовательно, log (основание a b) = 1 = c - (iii)

Теперь, f(N) = n^ c log^k(n) //k = 0 - (iv)

Используя (iii) и (iv) в уравнении (ii), мы получаем,

T(N) = O(N^c log^(k+1)N) = O(log(N)) - (v)

Это наихудшая временная сложность для бинарного поиска. Теперь рассмотрим наилучший случай, в котором выполняется единственное сравнение. Следовательно, N = 1. Итак, мы получаем,

O(log(1)) = O(1) (как log(1) = 1)

Следовательно, временные сложности для бинарного поиска в различных случаях заключаются в следующем:

Наилучший вариант - 

O (1)

Наихудший вариант

O(логарифм n)

Освоение структур данных и алгоритмов с использованием C и C++

Плюсы и минусы бинарного поиска в C

Преимущества:

• Довольно простой алгоритм, основанный на принципе "разделяй и властвуй"
• Намного быстрее по сравнению с линейным поиском. Линейный поиск требует N/2 и N сравнений для среднего и наихудшего сценариев. Бинарный поиск требует всего лишь log2 (N) и log2 (N) сравнений соответственно для среднего и наихудшего сценариев. Проще говоря, для линейного поиска в среднем требуется выполнить 500 000 сравнений для набора из миллиона элементов. Бинарный поиск, с другой стороны, требует всего 20 сравнений.
• Часто доступен в виде уже реализованной библиотечной программы

Недостатки:

• Сложнее, чем линейный поиск
• Большая потеря эффективности, если список не поддерживает произвольный доступ
• Работает только для списков, которые отсортированы и сохраняются отсортированными

Программа завершена!

Не существует единого авторитетного способа реализации бинарного поиска в C. Следовательно, возможности безграничны. Несколько примеров, упомянутых в статье, - лишь некоторые из многих.

Понимание того, как работает бинарный поиск, важно не только для достижения адекватности в C, но и в других языках программирования.

Знаете ли вы о каком-либо другом интересном / эффективном способе написания двоичного поиска в программе на C? Поделитесь с сообществом через специальное окно комментариев ниже.

Люди тоже читают:

• Лучшие учебные пособия по C ++
• Быстрая Сортировка На C
• Типы данных в C
• Разница между Float и Double
• Разница между передачей по ссылке и передачей по указателю
• Структура против объединения: различия, которые вы должны знать
• Лучшие курсы C
• C Вопросы и ответы для интервью