Рубрики

Программа C для двоичного поиска (рекурсивная и итеративная)

Мы в основном игнорируем половину элементов сразу после одного сравнения.

  1. Сравните х со средним элементом.
  2. Если x соответствует среднему элементу, мы возвращаем средний индекс.
  3. Иначе Если x больше среднего элемента, то x может находиться только в правой половине подрешетки после среднего элемента. Таким образом, мы вернемся к правой половине.
  4. Остальное (х меньше) повторяется для левой половины.

Рекурсивный:

C / C ++

#include <stdio.h>

  
// Рекурсивная функция двоичного поиска. Возвращает местоположение х в
// данный массив arr [l..r] присутствует, иначе -1

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("Element is not present in array")

                 : printf("Element is present at index %d", result);

   return 0;

}

итеративный

C / C ++

#include <stdio.h>

  
// Итеративная функция двоичного поиска. Возвращает местоположение х в
// заданный массив arr [l..r], если присутствует, иначе -1

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("Element is not present in array")

                 : printf("Element is present at index %d", result);

   return 0;

}

Пожалуйста, обратитесь к полной статье о бинарном поиске для более подробной информации!

Рекомендуемые посты:

Программа C для двоичного поиска (рекурсивная и итеративная)

0.00 (0%) 0 votes