-1

下面，我正在尝试使用递归函数编写一个简单的二进制搜索程序。当我运行它时，它会将要搜索的数组和键作为输入，但之后编译器会突然停止。也许是因为某处的无限循环。

#include<stdio.h>
int present_flag;
int binary_search(int array[],int low,int high,int key)
{
int mid=(high + low)/2;
if(low<=high)
{
    if (array[mid] == key)
    {
    printf("Key found at index %d \n",mid);
    return 1;
    }
        else if (array[mid] >key)
        return 0+binary_search(array,low,mid,key);
            else 
            return 0+binary_search(array,mid+1,high,key);;
}
else return 0;
}
main()
{
int array[9],i,n,key;
printf("Enter 9 numbers in asc order \n");
for(i=0;i<9;i++)
scanf("%d",&n);
printf("Enter number to be searched\n");
scanf("%d",&key);
present_flag=binary_search(array,0,8,key);
if (present_flag==0 )
printf("Number not present in array\n");
}
4

5 回答 5

1

填写第array一个

使固定 ：

for(i=0;i<9;i++) //Assuming your n is 9
  scanf("%d",&array[i]);
              ^^^ not n
于 2013-10-19T18:20:53.480 回答
1 
class BinarySearch
{
// Returns index of x if it is present in arr[], else
// return -1
int binarySearch(int arr[], int x)
{
    int l = 0, r = arr.length - 1;
    while (l <= r)
    {
        int m = l + (r-l)/2;

        // Check if x is present at mid
        if (arr[m] == x)
            return m;

        // If x greater, ignore left half
        if (arr[m] < x)
            l = m + 1;

        // If x is smaller, ignore right half
        else
            r = m - 1;
    }

    // if we reach here, then element was not present
    return -1;
}

欲了解更多信息， http://www.geeksforgeeks.org/binary-search/

于 2017-11-24T00:33:29.377 回答
0

为了响应 nitish712 的代码的简化版本，我们可以进一步简化代码的另一种方法是简单地返回 -1（而不是 0 用于元素不存在的情况），并在元素存在时返回 mid 本身：

int binary_search(int array[],int low,int high,int key)
{
int mid=(high + low)/2;
if (array[mid] == key)
{

    return mid;//This value can be utilized elsewhere in the code to check availability of the key in the array
}
if(low<high)
{
    if(array[mid] >key)
      return binary_search(array,low,mid,key);
    else 
      return binary_search(array,mid+1,high,key);
}
return -1;
}
于 2014-09-12T16:49:31.177 回答
0

首先它不是compiler被阻止的。编译器仅将您的程序转换为机器级指令。

其次，递归调用不会停止。因为您没有准确指定终止条件。因此，您的程序将executing无限期运行，直到堆栈空间用完并以segmentation fault.

更正后的代码如下（我在注释程序中指定了更改）：

#include<stdio.h>
int present_flag;
int binary_search(int array[],int low,int high,int key)
{

if(low==high)//if boundaries are same, just compare with the value and return
             //appropriately...
{
    if(array[low]==key){
    printf("Key found at index %d \n",low);
    return 1;
}
else
return 0;
}
int mid=(high + low)/2;
if(low<high)
{
    if (array[mid] == key)
    {
    printf("Key found at index %d \n",mid);
    return 1;
    }
        else if (array[mid] >key)
        return binary_search(array,low,mid,key);//need not put a zero explicitly...
            else 
            return binary_search(array,mid+1,high,key);
}
else return 0;
}
main()
{
int array[9],i,n,key;
printf("Enter 9 numbers in asc order \n");
for(i=0;i<9;i++)
scanf("%d",&array[i]);// <--- this should be array[i] and not n. 
printf("Enter number to be searched\n");
scanf("%d",&key);
present_flag=binary_search(array,0,8,key);
if (present_flag==0 )
printf("Number not present in array\n");
}

以更简化的方式重新编写函数，我们得到：

int binary_search(int array[],int low,int high,int key)
{
    int mid=(high + low)/2;
    if (array[mid] == key)
    {
        printf("Key found at index %d \n",mid);
        return 1;
    }
    if(low<high)
    {
        if(array[mid] >key)
          return binary_search(array,low,mid,key);
        else 
          return binary_search(array,mid+1,high,key);
    }
    return 0;
}
于 2013-10-19T18:29:30.003 回答
0

下面的代码片段是二进制搜索的简单实现，

bool search_recursive(int value, int values[], int lower, int upper) 
{
    if (lower > upper) return -1;
    int mid = (lower + upper) / 2;

    if (value == values[mid]) {
        return 1;
    }

    if (value > values[mid]) {
        // Search right half
        return search_recursive(value, values, mid + 1, upper);
    } else {
        // Search left half
        return search_recursive(value, values, lower, upper - 1);
    }
}
于 2016-11-22T02:59:20.007 回答