Блог

От нас требуется выполнить две функции: 1] Сортировка пузырьков и 2] Двоичный поиск. Если элемент не принадлежит массиву, функция 2]nd должна возвращать значение -1. В основной функции мы получаем входные данные, и если элемент не находится в массиве, мы должны вывести «Элемент не найден». Я написал программу в соответствии с особенностями, которые были заданы в вопросе.

1] — я функция, сортировка пузырьков работает нормально, но 2] — я функция выдает только «Элемент не найден» в качестве вывода, независимо от значения. Пожалуйста, предложите решение.

 void bubbleSortDec(int arr[10])
{
    int i=0,j=0,temp=0;
    for(i=0;i<9;i  )
    {
        for(j=0;j<9-i;j  )
        {
            if(arr[j]<arr[j 1])
            {
                temp=arr[j];
                arr[j]=arr[j 1];
                arr[j 1]=temp;
            }
        }
    }
}

int binarySearch(int arr[10], int x)
{
    bubbleSortDec(arr);
    int first, last=0, middle=0;
    first = 0;
  last = 10 - 1;
  middle = (first last)/2;

  while (first <= last) {
    if (arr[middle] < x)
      first = middle   1;
    else if (arr[middle] == x) {
      printf("%d found at location %d.n", x, middle 1);
      break;
    }
    else
      last = middle - 1;

    middle = (first   last)/2;
  }

  if (first > last)
    {
        return -1;
    }
 }   

int main()
{
        int arr[10];
        int i, x,k=0;
        printf("Enter 10 numbers n");
        for(i=0; i<10;i  )
            {
                scanf("%d", amp;arr[i]);
            }
        printf("Enter a number to be searched n");
        scanf("%d", amp;x);

            k=binarySearch(arr,x);
            if(k==-1)
                printf("Element not found n");
    }

 

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

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

 65 54 32 17 9
 

Чем вы ищете элемент midde, который равен 32. В вашем коде, если элемент, который вы ищете, меньше среднего элемента, вы продолжаете поиск в нижней части массива. Но в данном случае это неправильно. Потому что элементы, которые находятся в нижней части массива, больше, чем средний элемент. Вам нужно искать верхнюю часть массива.

Так что у вас есть два варианта.

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

 void bubbleSortDec(int arr[10])
{
    int i=0,j=0,temp=0;
    for(i=0;i<9;i  )
    {
        for(j=0;j<9-i;j  )
        {
            if(arr[j]>arr[j 1]) // Change is here. (this "<" to this ">")
            {
                temp=arr[j];
                arr[j]=arr[j 1];
                arr[j 1]=temp;
            }
        }
    }
}
 

Или вы можете изменить свой двоичный поиск на этот.

 int binarySearch(int arr[10], int x)
{
    bubbleSortDec(arr);
    int first, last=0, middle=0;
    first = 0;
  last = 10 - 1;
  middle = (first last)/2;

  while (first <= last) {
    if (arr[middle] > x) // Change is here. (this "<" to this ">")
      first = middle   1;
    else if (arr[middle] == x) {
      printf("%d found at location %d.n", x, middle 1);
      /*
      Returning anything except "-1" is okey. Because you only check for "-1".
      */
      return middle;
    }
    else
      last = middle - 1;

    middle = (first   last)/2;
  }
  /*
  If you couldn't find the element in while loop that 
  means the element is not in the array. You don't need to check it again.
  */
  return -1;
 }
 

И, наконец, я написал тот же код таким образом.

 #include <stdio.h>

#define SIZE 10

void swap(int *i1, int *i2) {
    int temp = *i1;
    *i1 = *i2;
    *i2 = temp;
}

void bubbleSort(int arr[SIZE]) {
    
    int i, j;
    for (i = 0; i < SIZE; i  ) {
        for (j = 0; j < SIZE - i - 1; j  ) {
            if (arr[j] > arr[j   1]) swap(arr   j, arr   j   1);
        }
    }
    
    return;
}

int binarySearch(int arr[SIZE], int x) {
    
    int first = 0, last = SIZE - 1;

    while (first <= last) {
        int middle = (first   last) / 2;

        if (arr[middle] == x) {
            return middle;
        } else if (x < arr[middle]) {
            last = middle - 1;
        } else {
            first = middle   1;
        }
    }

    return -1;
}   

int main() {
    
    int arr[SIZE];
    printf("Enter %d numbers n", SIZE);

    int i; for(i = 0; i < SIZE; i  ) scanf("%d", arr   i);

    printf("Enter a number to be searched n");
    int x;
    scanf("%d", amp;x);

    bubbleSort(arr);
    int k = binarySearch(arr, x);
    
    if (k == -1) printf("Element not found!n");
    else printf("Element found at index %d.n", k   1);

    return 0;
}