二进制搜索递归算法问题在C

好了，所以我给出的函数二进制搜索递归算法问题在C

int bin(int value, int size, int array[])

我应该内“[]数组”找到“价值”，但手头这里的问题是，在大多数情况下，我们沿着

int bin(int value, int max, int min, int array[])

递归线的东西，从逻辑上讲，是这部分容易得多由于我还可以通过我在，数量以及记忆的大小阵列。

int bin(int array[], int value, int min, int max) 
{ 
    if(max < min) 
     return -1; 
    else 
    { 
     int mid = min + (max - min)/2; 

     if(array[mid] > value) 
      return bin(array, value, min, mid-1); 
     else if(array[mid] < value) 
      return bin(array, value, mid+1, max); 
     else 
      return mid; 
    }

但是由于我只能传递1个整数，我该如何调整这个算法呢？实质上，我只能做这样的事情，但我知道它不会在逻辑上起作用。有没有办法，我可以看到数组的大小？我试过了，但是这些数字并没有被正确处理。

int bin(int array[], int value, int size) 
    { 
      int mid = size/2; 

      if(array[mid] > value) 
       return bin(array, value, size-(size/2)); 
      else if(array[mid] < value) 
       return bin(array, value, size+(size/2)); 
      else 
       return mid; 
    }

来源

2012-08-13 Ezrb3zr

请调整您的“家庭作业”标签等;你的约束肯定听起来像那样。提示：在C数组中实际上是指向底层数据类型的指针。所以你可以传递一个计算的参数'数组'到函数中。 – Adriaan 2012-08-13 11:55:59

@Adriaan：阵列不是指针。数组是数组。但是，不能将数组作为函数参数传递，并且在该上下文中，数组会衰减为指向第一个元素的指针。不过，这并没有改变数组的性质。 – 2012-08-13 12:00:53

你需要明确通过基部，以及：

int 
bin(int array[], int value, int size) 
{ 
     int mid = size/2; 

     if(array[mid] > value) 
      return bin(array, value, size/2); 
     else if(array[mid] < value) 
      return bin(&array[mid], value, size/2); 
     else 
      return mid; 
}

注意到“&阵列[MID]中的 ”if（数组[MID] <值）“ 的情况下

每次使用base + offset副最小/最大索引搜索数组的正确一半

来源

2012-08-13 11:50:13 tbert

在任何对bin（）的调用中，大小都不应该减小？ – erturne 2012-08-13 11:58:44

@erturne好抓;我的代码仍然没有解决所有问题（例如，数组中的奇数/偶数个元素），但基本思想是有。 – tbert 2012-08-13 12:18:17

是的。有效。谢谢！是的，有时在我的一些教授课程中有这些古怪的限制。 – Ezrb3zr 2012-08-13 12:44:27

使用具有不同参数集的方法的目的是将m使该方法易于为用户调用。这在递归中很常见。

有一种公开的方法可供用户使用，其签名为
int bin(int value, int size, int array[])。

然后应该有私人的内部帮手方法和
int bin(int value, int max, int min, int array[])签名。

问题是，有人调用这个方法会传递数组的大小，而不是开始和结束索引（因为对于他们来说，开始索引应该总是0，end应该总是大小为1 ），并且有一个带有预设参数的方法是不好的做法。

具有开始和结束值（最小值和最大值）的帮助程序方法在递归调用中用于更高效的计算，并且隐藏用户不必要的参数。然后

你的方法应该是这个样子：

int bin(int value, int size, int array[]) { 
    return bin(value, size - 1, 0, array); 
}

来源

2012-08-13 21:01:14

int * binSearch (int *arr,int size, int num2Search) 

{ 

    if(size==1) 

     return ((*arr==num2Search)?(arr):(NULL)); 

    if(*(arr+(size/2))<num2Search) 

     return binSearch(arr+(size/2)+1,(size/2),num2Search); 

    if(*(arr+(size/2))==num2Search) 

     return (arr+(size/2)); 

    return binSearch(arr,(size/2),num2Search); 

}

在我的功能，你会得到相同的参数和返回值的ADRESS。

来源

2013-12-14 17:38:33 user3102756

二进制搜索递归算法问题在C

回答

相关问题