再帰呼び出しを用いた二分探索(binary search)について教えてください(C言語)

Question

#質問内容
二分探索の関数の作成についてです。for文を用いて二分探索の関数binaryを作成することはできたのですが、再帰呼び出しを用いてbinary関数を作成する方法の一部が分かりません。以下にプログラムと分からない箇所を示します。他の部分は合っていると思うのですが、もしお気づきの点があればご教授頂けると幸いです。

ループを用いた二分探索のプログラム

#include <stdio.h>

/* プロトタイプ宣言 */
int binary(int n, int *data, int x);

/* メイン関数 */
int main()
{
   int data[8] = {1, 2, 3, 4, 5, 6, 7, 8};
   printf("%d", binary(8, data, 7));
}

/* binary関数の定義 */
int binary(int n, int *data, int x)
/* nは配列の要素数 */
/* xは検索したい数字 */
{
   int left = 0;
   int right = n - 1;

   while(left <= right)
   {
      int middle = (left + right) / 2;

      if(x == data[middle])
      {
         return middle + 1;
      }else if(x < data[middle])
      {
         right = middle - 1;
      }else
      {
         left = middle + 1;
      }
      return 0;
}

#再帰呼び出しを用いた二分探索のプログラム

#include <stdio.h>

/* プロトタイプ宣言 */
int binary(int n, int *data, int x);

/* メイン関数 */
int main()
{
   int data[8] = {1, 2, 3, 4, 5, 6, 7, 8};
   printf("%d", binary(8, data, 7));
}

/* binary関数の定義 */
int binary(int n, int *data, int x)
{
   int middle = (n - 1) / 2;

   if(x == data[middle])
   {
      return middle + 1;
   }else if(x > data[middle])
   {
      /* この部分が分かりません */
   }else
   {
      return binary(middle, data, x);
   }
   return 0;
}
   

#実行結果

7

Comments

[Zuishin]

シグネチャを変えたほうがわかりやすくなると思います。

int binary(int start, int end, int *data, int x)

でないとポインタ計算が入ってきます。

[退会済みユーザー]

コメントありがとうございます。
その方法での解答はできているのですが、関数の引数を3つにして作成せよとの条件があり困っているという状況です。情報不足で申し訳ありません。

[Zuishin]

それができてるなら後は機械的に足し算引き算するだけです。

まず引数 4 つのソースをもう一度書き、完全に動くことを確かめたら start が常に 0 になるように調整してみてください。そうすれば start は 0 に決まっているので渡す必要がなくなり、引数から外せます。

[Zuishin]

start を 0 にするには、次の関数に渡す際に start には start - start を渡し、data には data + start を、end には end - start を渡せばいいでしょう。

[退会済みユーザー]

そのstartの調整に困っているので、プログラムなどでもう少し詳しく教えていただけますか?

[退会済みユーザー]

ありがとうございます。一度試してみます。

[Zuishin]

今書きました。

[退会済みユーザー]

C# のタグがついてますが C/C++ の話では？ であれば間違っていますのでつけ直してください。

[退会済みユーザー]

ご指摘の通り間違えておりました。先ほど修正いたしました。

[退会済みユーザー]

色々考えてみたのですが、x > data[middle]の場合がやはり分かりません。先ほどのコメントにあったstartをどこでどのように定義すればよいかが特に分からないです。

[Zuishin]

ループの方、質問文を読む限りでは自分で書いたように見えるので、そのつもりで話しているんですが、違うんですか？

[退会済みユーザー]

ループのbinary関数、引数4つの場合のbinary関数は自分で作成しました。binary関数のはじめでstartを定義すると、再帰する際に毎回リセットされてしまうので困っています。

[退会済みユーザー]

自己解決いたしました。念のため報告させていただきます。

Answer 1

上記のように自己解決いたしました。

Comments

[退会済みユーザー]

すいません、勘違いがあったのでコメントを取り下げます。