• ベストアンサー

C++ BinarySearch について教えてください。

下記のようにClass Peopleの中にBinarysearchを 作りたいのですが、if (value == anArray[mid])else if (value < anArray[mid])の部分がタイプが違う為 コンパイルエラーになります。タイプを同じにすると 他の部分でエラーが出ます。どのように直したらよいのでしょうか?困っています! int People::binarySearch(PeopleArrayType anArray, int first,int last, PeopleType& value){ int index; if (first > last) index = -1; // value not in original array else{ int mid = (first + last)/2; if (value == anArray[mid]) index = mid; else if (value < anArray[mid]) index = binarySearch(anArray, first, mid-1, value); else index = binarySearch(anArray, mid+1, last, value);} return index;}

質問者が選んだベストアンサー

  • ベストアンサー
  • osamuy
  • ベストアンサー率42% (1231/2878)
回答No.3

PeopleTypeとかを適当に脳内補完してみた例: #include <iostream> #include <stdlib.h> using namespace std; class PeopleType { private: int value; public: PeopleType( int v = 0 ){ value = v; } int val( void ){ return value; } int operator = ( int v ){ value = v; } int operator == ( PeopleType b ){ return value == b.value; } int operator < ( PeopleType b ){ return value < b.value; } }; typedef PeopleType *PeopleArrayType; int binarySearch( PeopleArrayType anArray, int first, int last, PeopleType& value ){ int index; if (first > last) index = -1; // value not in original array else{ int mid = (first + last)/2; if (value == anArray[mid]) index = mid; else if (value < anArray[mid]) index = binarySearch(anArray, first, mid-1, value); else index = binarySearch(anArray, mid+1, last, value); } return index; } int main( int argc, char *argv[] ){ PeopleType Arr[ 4 ]; Arr[0] = 1; Arr[1] = 4; Arr[2] = 5; Arr[3] = 10; PeopleType it( atoi( argv[1] ) ); int rc = binarySearch( Arr, 0, (sizeof Arr / sizeof( PeopleType )) - 1, it ); cout << it.val() << " -> " << rc << endl; } 一応、gccで実行できました。 ただ、せっかくC++を使っているなら、STLのVectorとかの汎用コンテナクラスとを利用した方が良いと思います。binary_search()も既にありますし。 バイナリサーチの自習用なら、わざわざC++を使う必要もないかと。

october31
質問者

お礼

ありがとうございました!

その他の回答 (2)

回答No.2

> タイプを同じにすると他の部分でエラーが出ます。 タイプを一致させてもそこでエラーとならないように修正してください。 (呈示されたコードからは、具体的な修正点を指摘できません。)

  • taka_tetsu
  • ベストアンサー率65% (1020/1553)
回答No.1

PeopleArrayTypeってなんですか? これの定義は? 型が違うというエラーが出るからにはどんな型か記述していただかないと誰もわからないと思いますが。

関連するQ&A

  • Yesならこっちへ、NOならあっちへ(c++)

    取り組んでる課題で、Yとタイプしたら1のステップにいけて、Nとタイプしたら2のステップに行くというところでわからなくなってしまいました。Userにそういう選択させるのには何をどう書いたらいいのですか? --------------------------------------------------------------------- 問題:1から100までの整数をUserに選ばせ、Userに、「選んだ数字はXX以上ですか?」と質問を繰り返し、最後にUserの選んだ数字を当てるという課題です。(Userはそれに対してYes/Noでしか答えられません。) --------------------------------------------------------------------- int max=100; int min=0; int mid, x; int systemtype=y, sytemtype=n; main(){ while(1){ cout<<"1から100までで好きな数字を選んでね。"; cin>> x; if (n<=0 || n>=100){ break; } if (mid == (max + min)/2){ cout<<"選んだ数字は :" << mid << " より大きい? "<< endl; cout<<" y は YES, n は NO :" << endl; } else if(min == max){ cout<<"その数字は" << x <<endl; break; } else if(min == mid){ mid += ( max - mid)/2; cout<<"あなたの選んだ数は :" << mid <<" より大きい? "<<endl; } else if(max == mid){ mid -= (mid - min)/2; cout<<"あなたの選んだ数は:" << mid << " より大きい? "<< endl; } else cout<<"その数字は :"<< n <<endl; } return 0; }

  • C言語の二分探索法について質問です。

    C言語の2分探索法について質問です。 以下のようなプログラムを作りたいのですが,途中でよく分からなくなってしまいました。添削お願いします。 入力された整数を配列に順次格納する(必ず昇順になるように入力)。0が入力された時に整数の入力を終了し, 次に入力された数字を二分探索によって配列から探索し,その配列の添字番号を出力するプログラムを作成せよ。 実行例 (例1) (例2) 9 ←入力 1 ←入力 7 ←入力 42 ←入力 69 ←入力 99 ←入力 31 ←入力 13 ←入力 93 ←入力 0 ←入力 59 ←入力 5 ←入力 17 ←入力 not found ←出力 0 ←入力 7 ←入力 2 ←出力 プログラム #include <stdio.h> #include <stdlib.h> #define ARRAY_SIZE 10 int swap(int a, int b) { int c; c = a; a = b; b = a; } int main(void) { int array[] ; int low = 0; int high = n - 1; int mid; int key; int i, j, n; int data; struct node *p; puts("整数を入力して下さい。"); for(i = 0; i < ARRAY_SIZE && scanf("%d", array + i) == 1; ++i){ if(array[i] == 0) break; for(j = i; j > 0 && array[j-1] > array[j]; j--) swap(array[j-1], array[j]); } n = i; puts( "探索する値を入力して下さい" ); scanf( "%d", &key ); while( low <= high ) / { mid = (low + high) / 2; if( array[mid] == key ) { return ; } else if( array[mid] < key ) { low = mid + 1; } else { high = mid - 1; } } puts( "not found" ); return 0; }

  • C言語のアルゴリズム、マージソートについて質問です。

    C言語のアルゴリズム、マージソートについて質問です。 例えば下のプログラム #include <stdio.h> void merge(int first, int last, int *data, int *work); int main(void) { int data[9] = {1,8,3,6,5,4,7,2}; int work[9]; int i; merge(0,8,data,work); for(i = 0;i < 9;i++) printf("%d",data[i]); return 0; } void merge(int first, int last, int *data, int *work) { int middle, mae, ato, i; if (first == last) { return; } middle = (first + last) / 2; merge(first, middle, data, work); merge(middle + 1, last, data, work); i = first; mae = first; ato = middle + 1; while (mae <= middle && ato <= last) { if (data[mae] <= data[ato]) { work[i] = data[mae]; i++; mae++; } else { work[i] = data[ato]; i++; ato++; } } while (mae <= middle) { work[i] = data[mae]; i++; mae++; } while (ato <= last) { work[i] = data[ato]; i++; ato++; } for (i = first; i <= last; i++) { data[i] = work[i]; } } まずfirst=0,last=8でmerge関数に入り関数内8行目でmiddle=4となり、 10行目でfirst=0,last=4でmergeに入り同じく8行目でmiddle=2となり、 同じく10行目でfirst=0,last=2でmergeに入り同じく8行目でmiddle=1となり、 同じく10行目でfirst=0,last=1でmergeに入り同じく8行目でmiddle=0となり、 同じく10行目でfirst=0,last=0でmergeに入り3行目のifでreturnします。 そして前回のfirst=0,last=1,middle=0のmerge10行目に戻り, 12行目でfirst=1,last=1でmergeに入り3行目のifでreturnし、 12行目以下の作業をします。 そのまま一番下までいったあとはどうなるのでしょうか? また上で書いた手順もあっている自信はあまりないので ご指摘お願いします。

  • 再帰の仕方

    現在配列の出力結果が↓なのですがこれを array(2) { [0]=> string(6) "orange" [1]=> array(2) { [0]=> string(6) "apple" [1]=> array(2) { [0]=> string(6) "banana" [1]=> array(2) { [0]=> string(10) "Strawberry" } } } } ↓こっちのように変えたい場合の処理がどうしてもできません。 array(2) { [0]=> string(6) "orange" [1]=> string(6) "apple" [2]=> string(6) "banana" [3]=> string(10) "Strawberry" } 今自分がやってる途中のものです↓ $fruit = array("orange", array("apple", array("banana", array("Strawberry")))); function first_array($fruit) { foreach($fruit as $key => $value) { if(! is_array($value) === true ) { echo $value; } else { first_array($value); } } } $new_array = first_array($fruit); echo で orangeapplebananaStrawberry と表示はされるのですが、 配列に入れる方法がわかりません。 普通にこの部分を ~ if(! is_array($value) === true ) { $array[] = $value; } ~ とすると上書きされてしまっているのかな? 一個しかデータが残ってないのです・・・。 ご教授ください。

    • ベストアンサー
    • PHP
  • エラー C言語 プログラミングについて

    #include<stdio.h> int leapYear(int); int main(void){ int year,i; for(i=2001;i=2999;i++){ year=i; printf("%d leap = %d \n",i,leapYear(int year)); return 0; } } int leapYear(int year){ if(year%100==0){ return 0; } else if(year%400==0){ return 1; } else if(year%4==0 && year%100!=0){ return 1; } } をコンパイルすると11行目に式の構文エラーが出るんですが どうしてでしょうか?? 間違ってない気がするんですけど。。

  • C++ 動的確保について

    学校の演習課題で「クラス Array のメンバ変数を以下のように変更して,配列のサイズを実行時に決められるようにしたい.コンストラクタを適切に修正しなさい.配列のサイズはコンストラクタの引数で指定できるようにすること.main 関数内のオブジェクトの宣言部分を適当に変更して動作を確認しなさい.」という課題が出ました。 指示のメンバ変数の変更は、sizeを定数にしていたものを変数にし、arrayを配列からポインタにする点です。 もとのプログラムはI、私がいじったものがIIです。どうにもセグメンテーションフォルトから抜け出せなくて困っています。どのようにしたら題意のプログラムになるのでしょうか? よろしくお願いします。 ここからI~ #include <iostream> using namespace std; class Array{ private: const static int size = 6; int array[size]; public: Array( ); int getSize( ); void put( int index, int data ); int get( int index ); void show( ); }; Array::Array( ) { for ( int i = 0; i < size; i++ ) { array[i] = 0; } } int Array::getSize( ) { return size; } void Array::put( int index, int data ) { array[index] = data; } int Array::get( int index ) { return array[index]; } void Array::show( ) { cout << "| "; for ( int i = 0; i < getSize( ); i++ ) { cout << get(i) << " | "; } cout << endl; } int main( ) { Array array1; array1.put(1, 2); array1.put(4, 1); array1.show( ); return 0; } ~ここまでI ここからII~ #include <iostream> using namespace std; class Array{ private: int size; int *array; public: Array(int s); ~Array(); int getSize(); void put(int index, int data); int get(int index); void show(); }; Array::Array(int s) { size = s; array = new int; for (int i = 0; i < size; i++) { *array = 0; array++; } array -= size; } Array::~Array() { delete[] array; cout << "デストラクタが呼ばれました。配列の要素数分のメモリを開放します." << endl; } int Array::getSize() { return size; } void Array::put(int index, int data) { *(array + index) = data; } int Array::get(int index) { return *(array + index); } void Array::show() { cout << endl << "| "; for (int i = 0; i < getSize(); i++) { cout << get(i) << " | "; } cout << endl; } int main() { int s = 0; cout << "確保するサイズを入力してください:"; cin >> s; Array array1(s); array1.put(1, 2); array1.put(4, 1); array1.show(); return 0; } ~ここまでII

  • C言語 探索に関して

    C言語探索プログラムについて質問です。 #include <stdio.h> #define MAXSIZE 100 void swapData(int *x, int *y){ int tmp; tmp = *x; *x = *y; *y = tmp; } void simpleSort(int data[], int first, int last) { int i, j; for(i = first; i < last; i++){ for(j = i+1; j <= last; j++){ if(data[i] > data[j]) { swapData(&data[i], &data[j]); } } } } int ArrayBinarySearch(int data[], int n, int x) { int left = 0, right = n - 1, center; while(left <= right){ center = (left + right)/2; if(data[center]=x){ return center; }else if(x > data[center]){ left = center + 1; }else if(x < data[center]){ right = center - 1; } } return -1; } int main(int argc, char *argv[]) { int data[MAXSIZE]; int i, x; FILE *fp; scanf("%d", &x); fp = fopen(argv[1], "r"); for(i = 0; i < MAXSIZE; i++) { if (fscanf(fp,"%d", &data[i]) == EOF) break; } simpleSort(data, 0, i-1); printf("%d", ArrayBinarySearch(data, i, x )); return 0; } 数値が書かれたファイルを読み込んでソートした後に二分探索を行うプログラムをつくったのですが、うまく動きません。 どこがおかしいか教えてください。 お願いいたします。 ちなみに関数ArrayBinarySearchは目的の値が見つかれば配列中でのインデックスを、見つからない場合は-1を返す関数にしているつもりです。

  • while文の判定について(C言語)

    while文の判定についてです たぶんすごいつまらないミスなので時間の余っている方 ご指導ください<_ _> (自分ではいろいろ調べましたが原因がわかりません><、) returnやbreakを使わないで二分探索を終了させよとの問題で low-highで2ならばデータが見つかったとき 1ならば見つからなかったときという判定で whileで抜けさせたいのですがどうしても抜けません><、 論理演算子の使い方が間違っているのでしょうか? #include<stdio.h> #define N 10 int main(void) { static int a[]={2,3,4,11,31,50,55,70,77,80}; int key,low,high,mid; high=N-1; low=0; int i=0; printf("検索するdata ? :");scanf("%d",&key); ここです while((2!=(low-high)) || (1!=(low-high))){ mid=(low+high)/2; if(a[mid]==key){ low=mid+1; high=mid-1; } else if(a[mid]<key){ low=mid+1; } else{ high=mid-1; } } if(2==(low-high)){ printf("%2dは%2d番目にありました",key,mid); } else{ printf( "見つかりませんでした" ); } return 0; } while内でlow-highをprintfで出力しましたが2と1が出力されました

  • C#

    C#の質問です。 『クラスIntArrayを作成し、作成したクラスが正常に動作するか検証するためのクラスを作成してください。』 というプログラムを組んでおり、クラスIntArrayとその動作を検証するクラスを作成したのですが、クラスIntArrayについて「問題文で指定された通りに作成されていません。」という指摘を受けました。 何度も見直したのですが、どの部分が指定された通りになっていないのか、自分では見つけることが出来ませんでした; 私が作成したクラスIntArrayとその仕様については、下記のとおりです。 お分かりになる方がいらっしゃいましたら、ご助言をお願いいたします。 【クラスIntArray 仕様】 <インスタンス変数> int型の配列data <コンストラクタ> 以下の3種類を用意します。 ・int型の配列を受け取り、そのコピーを内部的に保持します。 ・第1引数で指定された要素数を持つ配列を確保し、全ての要素に初期値として第2引数で指定された値をセットします。 ・第1引数で指定された要素数を持つ配列を確保し、全ての要素に初期値としてゼロをセットします。 <メソッド> ・Sort 内部的に保持している配列を、引数の値がtrueであれば昇順、falseであれば降順にソートする ・Length IntArrayが保持している配列の要素数を取得する ・GetElement 引数に指定された要素番号の値を取得する ・SetElement 第1引数に指定された要素番号に第2引数で指定された値を格納する ・GetArray IntArrayが保持している配列のコピーを取得する 【作成したクラスIntArray】 using System; private int[] data; public IntArray(int[] array) { this.data = new int[array.Length]; array.CopyTo(this.data, 0); for (int index = 0; index < this.data.Length; index++) { // 先頭の要素以外を出力する場合 if (index > 0) { Console.Write(", "); } Console.Write(this.data[index]); } Console.WriteLine(); } public IntArray(int args1, int args2) { int[] myarray = new int[args1]; for (int index = 0; index < args1; index++) { myarray[index] = args2; } for (int index = 0; index < myarray.Length; index++) { // 先頭の要素以外を出力する場合 if (index > 0) { Console.Write(", "); } Console.Write(myarray[index]); } Console.WriteLine(); } public IntArray(int args) { int[] myarray = new int[args]; for (int index = 0; index < args; index++) { myarray[index] = 0; } for (int index = 0; index < myarray.Length; index++) { // 先頭の要素以外を出力する場合 if (index > 0) { Console.Write(", "); } Console.Write(myarray[index]); } Console.WriteLine(); } public void Sort(bool flg) { Array.Sort(this.data); //昇順にソート if (!flg)  //降順にソート { Array.Reverse(this.data); } for (int index = 0; index < this.data.Length; index++) { // 先頭の要素以外を出力する場合 if (index > 0) { Console.Write(", "); } Console.Write(this.data[index]); } Console.WriteLine(); } public int Length() { return this.data.Length; } public int GetElement(int args) { int getvalue = this.data[args]; return getvalue; } public void SetElement(int args1, int args2) { this.data[args1] = args2; } public void GetArray() { for (int index = 0; index < this.data.Length; index++) { // 先頭の要素以外を出力する場合 if (index > 0) { Console.Write(", "); } Console.Write(this.data[index]); } Console.WriteLine(); } }

  • visual C++だとコンパイルできるのに、borlandだとできません。

    borlandと、VisualC++の両方使っているのですが、VisualC++だとコンパイルでき、実行できます。 しかし、Borlandでコンパイルしようとすると、「宣言が正しく終了していない」とエラーが出てしまいます。 学校の課題で、Borlandでコンパイルしたいのですが、どうすればいいのか分かりません。 ソースを載せるので、どこがいけないのか、教えてください。 sin(x)の値を入力して、x度を求めるプログラミングです。 #include<stdio.h> #include<math.h> int main(void) { double x_mid, x0=0, x1=90, y_mid, y0, y1, M_PI=3.14159265358979; float y_ans; printf("sin(x)はいくつ?\n"); scanf("%f", &y_ans); for( ; ;) { x_mid=0.5*(x0+x1); y0=sqrt(1-cos(M_PI*x0/180)*cos(M_PI*x0/180)); y1=sqrt(1-cos(M_PI*x1/180)*cos(M_PI*x1/180)); y_mid=sqrt(1-cos(M_PI*x_mid/180)*cos(M_PI*x_mid/180)); if(y0-y_ans>0 || y1-y_ans<0) { printf("答えが出ません。もう一度sin(x)は?\n"); scanf("%f", &y_ans); continue; } if(fabs(y0-(double)y_ans) <= 0.000000001) break; else if((double)y_ans < y_mid) { x1=x_mid; } else { x0=x_mid; } } printf("sin(x)=%fのとき、xは%f度\n",y_ans, x0); return 0; }

専門家に質問してみよう