c - 在 C 中实现二进制搜索

Question

关于实现二进制搜索的快速问题 :-)。这是我现在拥有的功能，我还没有完全弄清楚为 i 传递正确数字的逻辑。然而，当我调试这个函数时，我发现当 value = values[i] (match) 时，发生了意想不到的行为。

我的意图是返回 true，从而触发匹配并退出函数。实际行为导致 return true； 然后返回false； (错误地)。有谁知道如何确保 return true；退出功能？或者指导我犯错的提示？非常感谢!

bool search(int value, int values[], int n){

   int i = ((n - 1) / 2); 

   if(value == values[i])
   {
      return true;
   }
   else if(value < values[i])
   {
      n = i;
      search(value, values, n);
   }
   else if(value > values[i])
   {
      n = (i * 1.5);
      search(value, values, n);
   } 
   return false; 
}

Answer 1

您缺少几个 return 关键字。

search(value, values, n);

应该是:

return search(value, values, n);

有两条这样的线。

如果没有那些 return 关键字，该函数总是会结束并返回 false。

更新，回应 OP 的评论

您的函数没有任何检查来确保 values 不会越界访问。我认为它永远不会尝试访问具有负索引的任何内容，但它有机会访问索引高于允许索引值的元素。我建议更改要使用的功能:

int search(int value, int values[], int start, int end)
{
   if ( start >= end )
   {
      return 0;
   }

   int mid = (start + end)/2; 

   if(value < values[mid])
   {
      return search(value, values, start, mid);
   }
   else if(value > values[mid])
   {
      return search(value, values, mid+1, end);
   } 
   else
   {
      return (value == values[mid]);
   }
}

并在从函数外部调用时使用正确的 start 和 end 值调用它。

int values[] = {1, 4, 6, 8};
bool found = search(2, values, 0, sizeof(values));