二分查找逻辑

Question

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

#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“。我的虫子在哪?！不是我找到的。谢谢

Answer 1

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

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

Answer 2

我测试了你的代码，它看起来工作正常。您必须记住，您输入的数字必须从小到大排序。

Answer 3

二分搜索包括通过将搜索范围划分为其原始大小的一半来将搜索范围缩小到一半。二进制搜索对排序的数组进行操作。它将此范围中的中间元素与要搜索的值进行比较，如果该值小于中间值，则在从第一个元素到中间元素的范围内查找该值，否则新的搜索范围将变为从中间到最后一个元素。这个过程会一直持续下去，直到定位到所需的元素或者下界大于上界。二分查找的效率在平均和最坏情况下为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…!”);
}