整数配列の中に整数5の配列の添字を出力したい

Question

whileを使った探索です。昇順に整数を入力し、その中で5の位置（配列の添字）を出力したいのですが、うまく行きません。5が存在しない場合はｰ1を出力させるのですが、自分のプログラムだと5を入力してもｰ1が出てきます。main関数内が間違っていると思うのですが、どのように治せばいいのでしょうか。（初歩的なミスだと思います。。。）

#理想の実行結果
入力 1 2 3 4 5
出力 4

#include <iostream>
#include <vector>
using namespace std;

int binary_search(vector<int>& numbers, int target, int low, int high){
  while(true){
    if(low>high)
      return -1;
    int mid=(low+high)/2;
    if(numbers[mid]==target)
      return mid;
    if(numbers[mid]<target)
      low=mid+1;
    else
      high=mid-1;
  }
}

int binary_search(vector<int>& numbers, int target){
  return binary_search(numbers, target, 0, numbers.size()-1);
}

int main(void){
  vector<int> numbers;
  int nums=0;
  cin >> nums;
  int idx=binary_search(numbers,5);
  if (idx>=0)
    cout << numbers[idx] << endl;
  else
    cout << "-1" << endl;
  return 0;
}

Comments

[cateye]

１．入力した数値(nums)は何処に格納するのですか？
２．数値(int)を入力くして、数字'5'を探しているのは何故でしょう？

[Ryuji_T]

1 それを考えていませんでした、、、配列を作ればいいのでしょうか。
2 課題の指示なので、特に理由はありません。

[cateye]

１．せっかく、vector使ってるんだからvectorに格納しましょう。
>課題の指示なので・・・数値を入力して文字を探すのですか？
・・・もし、そういう指示なら出題者に聞ましょう・・・“昇順に整数”とはなんですか？
また。２分検索にした理由はなんでしょう？
・・・関数名ダブってるし・・・まぁ。パラメータで分けられるけど・・・
蛇足：vectorのインデックスは'std::vector::size_type'です。

[Ryuji_T]

Binary Searchを使って数値を入力して特定の数字の位置を出力するプログラムを作るという課題です

[cateye]

数値と数字は違いますよ。'5'はASCIIで53(0x35)です、

[Ryuji_T]

これは失礼しました。入力するのは「数字」でした。

[cateye]

もう一つ、（配列の添字）と言っていますが、cout << numbers[idx] << endl;では見つかった文字を出力しています。
実行結果は添字になっていますね＾＾；

[episteme]

入力: 5 5 5 5 5 に対して 2を返すけど、それでいいのね?

[episteme]

> 入力するのは「数字」でした。

数字じゃないでしょ。「数値」でしょ。

[Ryuji_T]

会話をもう一度しっかり見直して、やっとお二方のおっしゃっていることがわかりました。「「数値」を昇順に入力して、「数値」の5の位置を探す」でした。しかし、(numbers,5)にしても結果は変わりませんでした。。。

[cateye]

“昇順に整数を入力”とありますから、入力: 5 5 5 5 5は違うのでは？
・・・最初に見つかった所、２が帰るのは間違いないです。
usr ~/Project/test % ./a.out
1 2 3 4 5 6
4
usr ~/Project/test % ./a.out
5 5 5 5 5
2

[episteme]

> “昇順に整数を入力”とありますから、入力: 5 5 5 5 5は違うのでは？

なんで? X[n] <= X[n+1] が成り立つなら昇順じゃないっけ?

[cateye]

昇順 →http://e-words.jp/w/%E6%98%87%E9%A0%86.html
残念ながら、X[n] <= X[n+1]かX[n] < X[n+1]か正確な定義は見つからなかったですが・・・
こちらは'＜’を使っています→https://byjus.com/maths/ascending-order
「To represent this order of numbers, we need to use the ascending order symbol “<“」

[episteme]

X[n] < X[n+1] が昇順の必要条件だとすると
数列 1 2 3 3 4 5 6 は昇順でないことになる...直感に反するんよなー。

[cateye]

この問題では1 2 3 3 4 5 6もありだろうけど、1 2 3 4 5 5 6 はまずいと思う。
まぁ、出題者はそこまで考えてないと思うけど・・・・

Answer 1

出来ましたか？

usr ~/Project/test % ./a.out 
1 2 3 4 5 6
4
usr ~/Project/test % ./a.out
1 2 3 4 6 7
-1

binary_search()は、パラメータと変数宣言以外ほとんどいじっていません。
・・・まぁ、一行でもブロックにするたちなので、{}は追加してありますが・・・
数字(char)と数値(int)に,対応しましたが分かりますか？

#include <iostream>
#include <vector>
//
using std::cin;
using std::cout;
using std::endl;
// コンパイルオプション→-DSCHAR で、文字検索
// オプション無しでint検索
#ifdef SCHAR
typedef char inputType;
const char   searchVal = '5';
#else
typedef int inputType;
const int   searchVal = 5;
#endif
//
typedef std::vector<inputType> iVec;
//
static size_t binary_search(iVec &numbers, inputType target)
{
    size_t low  = 0;
    size_t high = numbers.size( ) - 1;
    size_t mid;
    //
    while(true) {
        if(low > high) {
            return -1;  // size_tは非負なのでwarningが出る。
        }
        mid = (low + high) / 2;
        if(numbers[mid] == target) {
            return mid;
        }
        if(numbers[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
}
//
int main(void)
{
    iVec      numbers;
    inputType nums;
    //
    while(true) {
        cin >> nums;
        if(cin.eof( )) {  // UNIX系はCtrl+D,windowsはCtrl+Z
            break;
        }
        numbers.push_back(nums);
    }
    //
    int idx = int(binary_search(numbers, searchVal));
    cout << idx << endl;
    //
    return 0;
}

Comments

[Ryuji_T]

その後解説が行われ、理解しました。こちらのプログラムも参考にさせていただきます。ありがとうございます。

Answer 2

なにもわざわざ自作せんでも...

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int binary_search(const std::vector<int>& numbers, int target) {
    auto itr = std::lower_bound(numbers.begin(), numbers.end(), 5);
    return  (itr == numbers.end() || *itr != 5) ? 
              -1 : static_cast<int>(std::distance(numbers.begin(), itr));
}

int main(void) {
    using namespace std;
    vector<int> numbers = { 1, 2 ,3 ,4 ,5 };

    cout << binary_search(numbers, 5) << endl;
}

Comments

[cateye]

“Binary Searchを使って〜”が。どういった意図か分からないとなんとも言えませんね。

Answer 3

vector<int> numbers;
int nums=0;
cin >> nums;

numbers に値が入っていません。

でも、それ以外も NGっぽい。

Answer 4

あんましナカミ見てませんが、

int idx=binary_search(numbers,5);

なのでは

Comments

[Ryuji_T]

それでも試してみましたが、同じ結果になってしまいます。