在 C 中使用递归对数组进行二进制搜索

Question

我在 C 语言中使用递归对数组执行二进制搜索。但是，我一直在为搜索结果获取错误的索引值。请任何人测试运行不同值的代码并评论如何解决问题？

我的代码如下：

#include<stdio.h>
#include<process.h>
int arr[100];
int retindex(int, int, int);
void main()
{
    int i=0, num=0, digits=0, j=0, temp=0, element=0, beg=0, mid=0, last=0, index=0, flag=0;
    printf("%s\n", "Please enter the numeric array (Enter 10101 to terminate) : ");
    for(i=0; ; i++)
    {
        scanf("%d", &num);
        if(num==10101)
        break;
        else
        {
            arr[i]=num;
            ++digits;
        }
    }
    printf("\n\nSorting the numeric array...\nHence the entered numeric array is: \n\n");
    for(i=0; i<(digits-1); i++)
    {
        for(j=(i+1); j<digits; j++)
        {
            if(arr[i]>arr[j])
            {
                temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
            }
        }
    }
    for(i=0; i<digits; i++)
    printf("%d\t", arr[i]);
    printf("\n\nEnter the element you want to search for: ");
    scanf("%d", &element);
    printf("\n\nPerforming binary search...\n\n");
    beg=0, last=digits, mid=(beg+last)/2;
    index=retindex(element, beg, last);
    if(index==-1)
        printf("%s", "Element not found, exiting!");
    else
        printf("%s%d\n\n", "Hence the element being searched for lies at index number ", (index));
    getch();
}
int retindex(int ele, int be, int la)
{
    int mid;
    mid=(be+la)/2;
    if(ele<arr[mid])
        retindex(ele, be, (mid-1));
    else if(ele>arr[mid])
        retindex(ele, (mid+1), la);
    if(ele==arr[mid])
        return mid;
}

Answer 1

试试这个：

int retindex( int element, int lo, int hi )
{
    int mid = (lo+hi)/2;
    if( element < arr[mid] )
        return retindex( element, lo, (mid-1) );
    else if( element > arr[mid] )
        return retindex( element, (mid+1), hi );
    return mid;
}

Answer 2

    return retindex(ele, be, (mid-1));

else if(ele>arr[mid])

    return retindex(ele, (mid+1), la);

将是一个很好的起点。

Answer 3

您的函数永远不会 returns 在 main() 中查找的 -1。我发现进行二进制搜索的最佳方法是让顶部索引始终超出范围，即它永远不是候选者。

int retindex(int ele, int be, int la)
{
    int mid;
    mid = (be + la) / 2;
    if (mid == be) {
        if (ele == arr[mid])
            return mid;
        return -1;
    }
    if(ele < arr[mid])
        return retindex(ele, be, mid);
    if(ele > arr[mid])
        return retindex(ele, mid, la);
    return mid;
}

Answer 4

如果递归函数的 return 类型不是 void，则必须确保使用递归调用的 return 值。

if(ele<arr[mid])
    retindex(ele, be, (mid-1));  // Missing return 
else if(ele>arr[mid])
    retindex(ele, (mid+1), la);  // Missing return

在您的情况下，函数在进行递归调用时没有执行 return 就到达了函数的末尾。这会导致未定义的行为。

一个编程建议 -- 尽量减少在函数中使用全局变量。 retindex 可以很容易地更改为接受数组作为参数之一。

int retindex(int sorted_array[], int ele, int be, int la)
{
   int mid=(be+la)/2;
   if (mid == be) {
      if (ele == sorted_array[mid])
         return mid;
      return -1;
   }
   if(ele<sorted_array[mid])
      return retindex(sorted_array, ele, be, mid);
   else if(ele>sorted_array[mid])
      return retindex(sorted_array, ele, mid, la);
   else
      return mid;
}

在 C 中使用递归对数组进行二进制搜索

Binary Search on Arrays using Recursion in C

c

recursion