再帰関数呼び出しについて

[しき]

http://dixq.net/forum/viewtopic.php?f=3&t=19432
からの継続です。
【「二分探索をする関数」を、再帰関数呼出しをするものに作り替えよ。】
という問題なのですが何を加えればいいかわかりません・・。ネットや参考書で調べてみたのですが出てくるのはn!の例題だけで二分探索はどうするのかというのが分からなくなってしまいました。解決策を教えてください。よろしくお願いします。

コード:

int binsearch(int a[DATA],int n,int x)
{
  int max;
  int min;
  int mid;
  while (scanf("%d", &x)==1) {
    min=0;
    max=n;
    while(min <= max ) {
      mid = (min + max) / 2;
      if (a[mid]==x) {
        break;
      } else if (a[mid] < x) {
     min = mid + 1;
      } else if (a[mid] > x){
        max = mid - 1;
      }
    }



    if(a[mid]==x){
      printf(" x=%d ---> %d\n",x ,mid-1 );
}
    else {
      printf("見つかりませんでした。\n",x);
    }
}//二分探索する関数

[Math]

http://dixq.net/forum/viewtopic.php?f=3&t=19403#p146664
の
No:3 のようにしてはどうでしょうか。

[しき]

Mathさん遅くなりましたが返信ありがとうございます。
http://dixq.net/forum/viewtopic.php?f=3&t=19432
こちらのトピックで参考にさせていただきました。

[しき]

提示されたコードと前回のトピックを参考にコードを作ってみたのですが、うまく値を探せません。何が原因なのでしょうか？
教えてください。よろしくお願いします。

コード:

#include <stdio.h>
 
#define DATA 10000
 
int fileinput(const char *filename, int a[])
{
    int n, x;
    FILE *fin = fopen(filename, "r");
    if (fin == NULL) return -1;
    for (n = 0; n <= DATA && fscanf(fin, "%d", &x) == 1; n++)
        if (n < DATA) a[n] = x;
    fclose(fin);
    return n;
}
 
void selectionsort(int a[], int n)
{
    int i, j, k, tmp;
    for (i = 0; i < n - 1; i++) {
        j = i;
        for (k = i + 1; k < n; k++)
            if (a[j] > a[k]) j = k;
        tmp = a[j]; a[j] = a[i]; a[i] = tmp;
    }
}
 
int binsearch(int x, int a[], int min, int max)
{
    while (min <= max ) {
        int mid = (min + max) / 2;
        if (a[mid] == x)
            return mid;
        if (a[mid] < x)
            return binsearch(x,a,min,mid+1)
        else if (a[mid] > x)
           return binsearch(x,a,mid-1,max)
    }
    return -1;
}
 
int main(void)
{
    char filename[200];
    int a[DATA];
    int n, x, i;
 
    printf("ファイル名: ");
    scanf("%s", filename);
    n = fileinput(filename, a);
    if (n == -1) {
        puts("ファイルをオープンできません");
        return 1;
    }
    if (n > DATA) {
        puts("データが多すぎます");
        return 2;
    }
    selectionsort(a, n);
    puts("探したい値を入力してください");
    while (scanf("%d", &x) == 1) {
        i = binsearch(x, a, 0, n - 1);
        if (i >= 0)
            printf(" x = %d ---> %d\n", x, i);
        else
            puts("見つかりませんでした");
    }
    puts("またお会いしましょう");
    return 0;
}

実行結果です。

コード:

探したい値を入力してください
1
見つかりませんでした
2
見つかりませんでした
3
見つかりませんでした
4
見つかりませんでした
5
見つかりませんでした
6
x = 6 --> 2
0
見つかりませんでした
43
見つかりませんでした
123
見つかりませんでした

[かずま]

そのソースは、コンパイルエラーになります。
セミコロンを付けて、コンパイルエラーにならないようにしても、
実行結果のようにはなりません。
実行結果に対応するソースを提示してください。

実行できないので、紙に鉛筆で次のように書きだしてみましょう。

コード:

n = 5
a [0] [1] [2] [3] [4]
   1   2   6  43  123

x = 1
 
[1] binsearch
min = 0, max = 4 --> mid = 2
a[mid] = 6
a[mid] > x だから、mid-1 = 1, max = 4

[2] binsearch
min = 1, max = 4 --> mid = 2

思った通りに進行していますか？

[しき]

すみません提示するコード間違えてました。正しくは、下記のコードの変更前のものです。
紙に書くと自分が何を間違えているか確認することができました。ありがとうございます。
きちんと動作するのでこれにて解決とさせていただきます。
最終コードを載せておきます。

コード:

#include <stdio.h>
#include <stdlib.h>
#define DATA 10000

int fileinput(const char *filename, int a[])
{
 int n, x;
 FILE *fin = fopen(filename, "r");
 if (fin == NULL) return -1;
 for (n = 0; n <= DATA && fscanf(fin, "%d", &x) == 1; n++)
 if (n < DATA) a[n] = x;
 fclose(fin);
 return n;
}//ファイルからデータを入力する関数

void selectionsort(int a[DATA],int n )
{
  int i,j,k;
  int tmp;
  for(i=0; i < n-1; i++){
    j=i;
    for(k=i+1; k < n; k++){
      if (a[j] > a[k]){ j=k; }
    }
    tmp=a[j];
    a[j]=a[i];
    a[i]=tmp;
  }
}//データを整列する関数

int binsearch(int a[DATA],int x,int min,int max)
{
  if (min <= max){
    int mid = ( min + max )/ 2;
    if (a[mid] == x)
      return mid;
   if (a[mid] < x)
     return binsearch(a,x,mid+1,max); //変更前(a,x,min,mid-1)→変更後(a,x,mid+1,max)
     else if (a[mid] > x)
       return binsearch(a,x,min,mid-1);//変更前(a,x,mid+1,max)→変更後(a,x,min,mid-1）
  }
  return -1;

}//二分探索する関数

int main(void)
{
  char filename[20];
  int n,x,y;
  int a[DATA];

  printf("ファイル名＝");
  scanf("%s",filename);
  n=fileinput(filename,a);
  if(n==-1){
    printf("ファイルをオープンできません。\n");
    return 1;
  }
  if (n >DATA ){
    puts("データが多すぎます\n");
    return 2;
  }
    selectionsort(a,n);
    puts("探したい値を入力してください");
    while (scanf("%d",&x) == 1){
      y = binsearch(a,x,0,n-1);

        if (y >= 0)
          printf("x = %d --> %d\n",x,y);
        else
          puts("見つかりませんでした");
    }
  printf("またお会いしましょう\n");
  return (0);
}

[Math]

[雑談：注意]
int imid = imin + (imax - imin) / 2;
を
int mid = ( min + max )/ 2;
にするには良くある間違いで　max + min が int の限界を超えてオーバーフローしてしまう可能性があります。

[しき]

なるほど・・。
書き直しておきます！

[Math]

（この場合は10000以下だからいいのですが...）

[Math]

[雑談]失礼。
実装上の間違い
ドナルド・クヌースは "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" と述べており、二分探索が正確に実装されていないことは多い。Richard E. Pattis の1988年の調査では、書籍20冊のうち15冊が誤っていた。

良くある間違いの一つは、imin + (imax - imin) / 2 を (imax + imin) / 2 としてしまう事である。これでは、imax + imin が int の限界を超えてオーバーフローしてしまう可能性がある。Java の標準ライブラリの Arrays.binarySearch() では JDK 1.2 (1998年) から間違えており、Java 6 (2006年) で修正された

[しき]

なるほどそうだったんですね・・。
int の限界は2^31 -1と聞いたのですが実際に二分探索でオーバーフローさせるにはめちゃくちゃ多いデータを用意しなくてはならないってことなんですかね・・。二分探索、奥が深いです・・。
まあなにはともあれ勉強なりました！ありがとうございます！