二进制搜索的逻辑

我读了数据结构手册中的二进制搜索的伪代码，然后开始编写代码。我写的代码是：二进制搜索的逻辑

#include <iostream.h> 
#include <conio.h> 
template <class T> 

int BSearch(T x[], const int n, T item) 
    { 
    int loc, first = 0, found = 0, last = n-1; 
     while(first <= last && !found) 
     { 
      loc = (first + last)/2; 
      if(item < x[loc]) 
       last = loc - 1; 
      else if(item > x[loc]) 
       first = loc + 1; 
      else 
       found = 1; 
     } 
     return found; 
    } 

int main() 
    { 
    const int n =5; 
     int x[n],item; 
     cout << "Pls enter " <<n<<" number(s): "; 

     for(int i = 0; i < n;i++) 
     cin >> x[i]; 
     cout << "Pls enter the item to Search: "; 
     cin >> item; 
     if(BSearch(x,n,item)) 
     cout << "\n\t Item Exist"; 
     else 
     cout << "\n\t Item NOT Exist"; 

     getch(); 
     return 0; 
    }

没有任何错误，但是存在逻辑错误。它只是从BSearch函数返回0值，我只是得到这个消息“Item Not Exist”。我的错误在哪里？我没有找到它。谢谢

来源

2012-12-17 John Martin

当你用调试器加入代码时发生了什么？ –

@irrelephant：在书中作者说“last < - loc -1” –

请注意，在_Sorting and Searching_的6.2.1节中，Knuth记录了第一个二进制搜索例程于1946年发布，但第一个发布的二进制搜索没有错误的程序直到1962年才出现。令人惊讶地很难得到正确的二进制搜索！ –

二进制搜索仅适用于有序列表。但是您不要订购从std::cin获得的列表，因此您从二分查找中得到了错误的结果。

要解决这个问题，您必须将输入限制为预先排序的列表，或者您必须在执行二分查找之前首先对列表进行排序。

来源

2012-12-17 01:01:56 Haatschii

你能帮我写一个适用于无序列表的二进制代码吗？ –

@JohnMartin - 在无序列表上工作的唯一Binary搜索算法是在搜索之前对其进行排序的算法。 –

@JohnMartin Karthik T说的是真的。因此，如果是作业，您应该再次阅读说明书，如果您可以将已排序的列表视为理所当然。我会怀疑是否，因为有效地对列表进行排序比双向搜索更有效。如果你确实需要它的一些程序，我会建议你使用标准库算法。特别是http://en.cppreference.com/w/cpp/algorithm/find和http://en.cppreference.com/w/cpp/algorithm/sort可能会有帮助。 – Haatschii

我试了你的代码，它似乎工作正常。你必须记住，你输入的数字必须从小到大排列。

来源

2012-12-17 01:23:14

二进制搜索涉及通过将范围划分为原始大小的一半来将搜索范围缩小为一半。二进制搜索按排序后的数组运行。它将该范围中间的元素与要搜索的值进行比较，如果值小于中间值，则在从第一个元素到中间的范围内查找该值，否则新搜索范围将变为中间到最后的元素。这个过程一直持续到所需的元素被定位，或者下限变得大于上限。二进制搜索的效率平均为O（log2n），最差情况下为O（1）。执行二进制搜索的'C'程序如下：

/* Binary Search */ 
#include <stdio.h> 

#define MAX 10 

int main(){ 
int arr[MAX],i,n,val; 
int lb,ub,mid; 
printf(“nEnter total numbers?”); 
scanf(“%d”,&n); 
for(i=0;i<n;i++){ 
printf(“nEnter number?”); 
scanf(“%d”,&arr[i]); 
} 
printf(“nEnter the value to search?”); 
scanf(“%d”,&val); 
lb=0;ub=n-1; 
while(lb<=ub){ 
mid=(lb+ub)/2; 
if(val<arr[mid]) 
ub = mid-1; 
else if(val>arr[mid]) 
lb = mid+1; 
else { 
printf(“nNumber found…!”); 
return; 
} 
} 
printf(“nNumber not found…!”); 
}

来源

2012-12-18 05:56:21

二进制搜索的逻辑

回答

相关问题