binary search

アルゴリズムとしては基本中の基本なのですが、たまに書いてはよく混乱するのでここらでひとつ問題を作ってみました。暇な人はどうぞ。

以下の(A), (B) は共にバイナリサーチの実装です。
どちらも配列内で a[0] から a[n-1] まで、n 個の要素がソートされた状態で格納されているとして、この中から特定の要素（のインデックス）を探します。ただし(A),(B)で引数の与え方は異なります。

さて、これらはどちらもバグを含みます。
それを指摘し、1バイト編集(add/delete/change)してfixしてください。

(A)

#define NOT_FOUND -1
/**
 * usage: binarySearch(x, a, 0, n-1);
 * ( n = sizeof(a)/sizeof(a[0]) )
 */
int binarySearch(char x, char a[], int l, int r) {
  while (l < r) {
    int m = (l + r) / 2;
    if (x == a[m]) {
      return m;
     } else if (x < a[m]) {
       r = m - 1;
     } else {
       l = m + 1;
     }
  }
  return NOT_FOUND;
}

(B)

#define NOT_FOUND -1
/**
 * usage: binarySearch(x, a, 0, n);
 * ( n = sizeof(a)/sizeof(a[0]) )
 */
int binarySearch(char x, char a[], int l, int r) {
  if (l > r) return NOT_FOUND;
  int m = (l + r) / 2;
  if (x == a[m]) {
    return m;
  } else if (x < a[m]) {
    return binarySearch(x, a, l, m);
  } else {
    return binarySearch(x, a, m+1, r);
  }
}

ヒント、というか補助問題:

• (A)には、要素を含んでいるのに Not Found を返す入力が存在します。それを挙げなさい。
• (B)には、無限ループを引き起こす入力が存在します。それを挙げなさい。