3

我在一本数据结构书籍中阅读了二进制搜索的伪代码，然后我开始编写代码。我写的代码是：

#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 值，我只是收到此消息“项目不存在”。我的虫子在哪里？！我没找到。谢谢

4

3 回答 3

8

二进制搜索仅适用于有序列表。但是您没有对从中获得的列表进行排序std::cin，因此您从二进制搜索中得到错误的结果。

要解决此问题，您要么必须将输入限制为预排序列表，要么必须在执行二分搜索之前对列表进行初始排序。

于 2012-12-17T01:01:56.527 回答
4

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

于 2012-12-17T01:23:14.507 回答
0

二进制搜索涉及通过将范围划分为其原始大小的一半来将搜索范围缩小到一半。二进制搜索对排序数组进行操作。它将这个范围中间的元素与要搜索的值进行比较，如果值小于中间值，则在从第一个元素到中间的范围内查找该值，否则新的搜索范围变为中间到最后一个元素。这个过程一直持续到找到所需的元素或下限变得大于上限。二分搜索的效率在平均和最坏情况下为 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-18T05:56:21.787 回答