无法用 C 语言获得此二进制搜索程序的所需输出

Question

我们需要创建两个函数，1] 冒泡排序和 2] 二分查找。如果一个元素不属于数组，则 2]nd 函数应该 return -1。在 main 函数中我们获取输入，如果元素不在数组中，我们应该打印“Element not found”。我已经根据问题中要求的细节编写了程序。

第 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", &arr[i]);
            }
        printf("Enter a number to be searched \n");
        scanf("%d", &x);

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

Answer 1

您的冒泡排序以递减顺序对数组进行排序。这当然不是问题，你仍然可以那样使用，但你需要改变你的二进制搜索。问题就出在这里。

假设您有一个按降序排列的数组，假设您正在搜索 17.

65 54 32 17 9

比您要查找的中间元素是 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", &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;
}

无法用 C 语言获得此二进制搜索程序的所需输出

Can't get the desired output of this binary search program in c language

c

arrays

error-handling

function

binary-search