探索キーがデータ内に複数存在するときの二分探索（ｃ言語）

Question

前提・実現したいこと

ファイルからデータを読み込んでそのデータを選択ソートで整列させた後、二分探索法で、探索キーと一致する配列要素の添え字を全て表示するプログラムを作成しています。しかし、探索キーと一致する要素が複数存在するときはその添え字の全てを表示するプログラムを作成したいのですが、どうやっても1つしか表示できません。改良方法が知りたいです。まだまだプログラミング初学者なため出来るだけ簡単に分かりやすくご教授いただければ幸いです。よろしくお願いします。（ｃ言語）
**

発生している問題・エラーメッセージ

探索キーと一致する要素が複数存在するときその添え字の全てを表示したいが1つしか表示できず、全ての添え字を表示する方法がわからない。

### 該当のソースコード
#include <stdio.h>

#define MAXDATE 10000

#define _YES 1
#define _NO  0

int main(void)
{
 int n, i, j, k, x;
 int v[MAXDATE];
 int highid, lowid, midid;
 int tmp;
 char filename[20];
 FILE *fin;

 puts("ファイル名を入力してください。");//データの読み込み
 printf("file name =");
 scanf("%s", filename);

 if ((fin = fopen(filename, "r"))==NULL) {
   printf("ファイルを開くことが出来ません。\n");
   return 1;
   }

 n = 0;
 while (fscanf(fin, "%d", &v[n])==1) n++;
   fclose(fin);

 for (i = 0; i < n; i++) {
   fscanf(fin, "%d", &v[i]);
   } 
 
 for (i = 0; i < n - 1; i++) {　//選択ソートによるデータの並び替え
      j = i;
    for (k = i + 1; k < n; k++) {
       if (v[j] > v[k]) {
          j = k;
         }
       }
    tmp  = v[j];
    v[j] = v[i];
    v[i] = tmp;
  }

 while (scanf("%d", &x)==1) {　//二分探索による探索

  highid = n - 1;
  lowid  = 0;

  int found = _NO;
    while (lowid <= highid) {
      midid = (lowid + highid) / 2;
      if (v[midid] == x) {
        found = _YES;
        break;
      }
       else if (v[midid] < x) {
        lowid = midid + 1;
      }
       else {
        highid = midid - 1;
      }
   }

  if (found == _YES) {
      printf("%dはv[%d]と一致しました。\n", x, midid);
      }
  else {
      printf("%dはデータから見つかりませんでした。\n", x);
      }
  }

 printf("さようなら。\n");

 return 0;
 }

```ｃ言語

Comments

[jimbe]

提示するコードには行番号は付けないでください。
コードは回答側がコピペして実際に動作を確認する場合等に使用します。大抵の場合行番号はエディタによって付けられますので、コピペの際に修正しなければならず、修正間違い等によって動作確認が失敗する可能性があります。

[jimbe]

修正ありがとうございます。

Answer 1

どうやっても1つしか表示できません。改良方法が知りたいです。まだまだプログラミング初学者なため出来るだけ簡単に分かりやすくご教授いただければ幸いです。

見つかったら、同じ値を持つものの先頭と最後を探して表示すればよいでしょう。

-      printf("%dはv[%d]と一致しました。\n", x, midid);
+      i = j = midid;
+      while (--i >= 0 & v[i] == x) ;
+      while (++j < n && v[j] == x) ;
+      while (++i < j) printf("%dはv[%d]と一致しました。\n", x, i);

追記
while (--i >= 0 & v[i] == x) ; の & は && の間違いです。
& だと、第1項の --i >= 0 と第2項の v[i] == x の両方を評価し、
その結果のビットAND演算を実行します。
i が -1 になった時 --i >= 0 の判定はできますが、
v[i] == x で v[-1] を参照するので未定義動作になります。
&& だと、第1項の --i >= 0 の評価結果が 0 だと
第2項の v[i] == x は評価しないから問題ありません。

コードの意味ですが、例えば、
v[] = { 1, 2, 3, 3, 3, 4, ... }、x = 3 のとき
v[2], v[3], v[4] が求めるものです。
midid が 3 だったとすると、
最初の whileループを終了した時、i は 1 になります。
次の whileループを終了した時、j は 5 になります。
最後の whileループで、i が 2、3、4 と変化し、結果を表示します。

Comments

[4431]

アドバイスの通りにプログラムを修正したら成功しました。本当にありがとうございます。

[kazuma-s]

なぜ成功したのかコードの意味を理解していますか？
実はこのコードは間違っています。

[4431]

すみません。意味を正確には理解できていません。詳しく教えて頂けませんでしょうか？

[4431]

解答して頂きありがとうございます。参考にさせていただきます。

Answer 2

#include <stdio.h>

int main() {
    int v[10] = { 1, 2, 3, 3, 3, 4, 5, 6, 7, 8 };

    int n = 10; // 要素数
    int x = 3;  // 検索対象

    int count = n;
    int lowid = 0;

    while ( 0 < count ) {
        int count2 = count / 2;
        int midid = lowid + count2;
        if (v[midid] < x) {
             lowid = midid + 1;
             count = count2 + 1;
        } else { // v[midid] == x となってもloopを抜けない
             count = count2;
        }
    }
    while ( v[lowid] == x ) {
        printf("v[%d] = %d\n", lowid, v[lowid]);
        ++lowid;
    }
    return 0;
}

Answer 3

57行目でbreakするかわりにprintfすれば良いでしょう。

Comments

[episteme]

printしたいんじゃなくて、検索対象と等しい要素の最小index/最大indexを求めたいのではないかなー...