二进制搜索在 C 中不起作用

Question

我有以下二进制搜索算法：

int search_binary(int* tab,int size, int a)
{
    int lower=0,upper=size-1,middle=(lower + upper)/2;
    while(lower < upper)
    {
        if(tab[middle] == a)
            break;
        else if(tab[middle] < a)
        {
            upper = middle - 1;
            middle = (lower + upper)/2;
        } else {
            lower = middle + 1;
            middle = (lower + upper)/2;
        }

    }

    if(tab[middle] == a)
        return middle;
    else
        return -1;

}

它要么 return -1 如果我插入一个存在的数字，要么它 return 是错误的索引。

示例数据：

table: 2个 2个 4个 5个 7 7 8个 8个 8个 9

搜索号码： 7

结果：索引为：4

table: 1个 2个 3个 4个 6个 6个 6个 7 8个 9

搜索号码： 4

结果：索引为：-1

Answer 1

else if(tab[middle] < a)
    {
        upper = middle - 1;
        middle = (lower + upper)/2;
    }

从这里看来，您似乎希望数组按降序排列。事实上，给它一个这样排列的数组，它对我有用。

只需将 if 更改为：

if(tab[middle] > a)

使其适用于按递增顺序排列的数组

Answer 2

函数中的循环略有变化 -

int search_binary(int* tab,int size, int a)
{
   int lower=0,upper=size-1,middle=(lower + upper)/2;
   while(lower < upper)
  {
    if(tab[middle] == a){               // if found 
        return middle;                  // return index 
      }
    else if(tab[middle] < a)            // if a is greater 
    {
        lower= middle ;          //lower is updated to middle,search in part above middle 
        middle = (lower + upper)/2;
    } else {
        upper = middle - 1;     //else upper is updated search in part lower than middle
        middle = (lower + upper)/2;
    }

  }
 return -1;
}

当 tab[middle]<a 然后由于 upper 的更新，它会搜索 0 to middle -1 部分的号码，而 index.I已使用变量中的正确更改更新您的代码。

二进制搜索在 C 中不起作用

binary search doesn't work in C

c

binary-search