バイナリ検索C++（このコードの欠陥は何ですか）

Question

ハッカーのバイナリ検索チュートリアルを解決していましたが、明らかに何かが間違っています...入力形式は次のとおりです。 N =配列内の要素数はありません 昇順 Q =テストケース 要素の数は、Qテストケースで発見される

#include <iostream> 
using namespace std; 
int main() 
{ 
    int n;cin>>n; 
    int ar[n];for(int y=0;y<n;y++) cin>>ar[y]; 
    int q;cin>>q; 

    for(int u=0;u<q;u++) 
    { 
     int j;cin>>j; 
     int low=0,high=n-1,mid=(low+high)/2; 

     while(low<high) 
     { 
      mid=(low+high)/2; 
      if(ar[mid]<j) low=mid+1; 
      if(ar[mid]>j) high=mid-1; 
     } 

     cout<<mid-1<<endl; 
    } 
    return 0; 
} 

編集：

1. なぜ可変サイズの配列を宣言するのがそんなに嫌いなのですか？ベクトルよりも書く方がずっと効率的です...そしてC++ 99標準によれば完全に合法です。これをC++ 11標準で使用しています私のすべてのプログラムは可変サイズの配列で動作します。

2. この欠陥を指摘していただきありがとうございます。 j == ar [mid]の場合は未処理です。コードはその後に動作するはずです。

3. それは自動チェックされている..私はすでにこれがhackerearth上の問題で述べたように、完全に不要...答えのプレゼンテーションや入力を得ることについて忘れて...

4. 回答台無しに出力形式をこれがして提示私の最初の質問は、コミュニティがとても助けになりました。 :)。また、なぜそれが..コードを挿入するのは難しい..私は、インサートのコードを試してみましたコピーし、その中に貼り付ける..しかし、それは動作しませんでしたされ、私は3であり、4つのスペース:(

Answer 1

への手動のインデントすべてのものを持っていましたあなたはこのコードを動作させるために変更する必要がありますもの。

1. あなたはときar[mid]==jケースを扱うのを忘れていました。この場合、whileループwhile(low<high)が無限になります。

2. cout<<mid-1<<endl;このラインはあなたの中ということを意味しますループmidが常により大きな値を持つインデックスを指していることを確認します。これは、whileループを書いた方法を考慮していません。

3. int n; cin>>n; int ar[n];これは、nが定数ではないため、実際には悪い方法です。あなたはこのような検索の部分を編集することができstd::vector<int> ar(n)代わりのint ar[n]

を使用してみてください：すべての

int low=0,high=n-1,mid; 
while(low<high) 
{ 
    mid=(low+high)/2; 
    if(ar[mid]>j) high=mid-1; 
    else low=mid+1; 
} 
if(high>=1 && high<=n && ar[high-1]==j) cout<<(high-1)<<endl; 
else { // you didnt find the value} 

Answer 2

まず、あなたは可変サイズの配列を宣言することはできません。このような問題を解決する

そして、次のようにバイナリ検索を行い、

int j; 
    cin >> j; 

    int low = 0, high = n - 1, mid = (low + high)/2; 

    while (low<=high) 
    { 
     mid = (low + high)/2; 
     if (ar[mid] == j) 
      break; 

     if (ar[mid]<j) low = mid + 1; 
     if (ar[mid]>j) high = mid - 1; 
    } 
    if (ar[mid] == j) 
     cout << j << " is found and index is = " << mid << endl; 
    else 
     cout << j << " is not found" << endl;