二元搜索的逻辑

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,因此你的二进制搜索会得到错误的结果.

要解决这个问题,您必须将输入限制为预先排序的列表,或者在进行二进制搜索之前必须先对列表进行排序.