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 に答える