Algorithm 問題を解く4 - 長さ不明の配列のサーチ

問題

Suppose you do not know the length of A in advance; accessing A[i] for i beyond the end of the array throws an exception.
Find the index of the first occurrence in A of a specified key k; return -1 if k does not appear in A.
(出典: Algorithms for interviews )

ヒント

終点がわからなければ探すしかない．終点がわかってからサーチ．ひと手間増えただけのこと．
問題はソート済みかどうかは言っていないがとりあえずソート済みということにしておこう．

解

まずは終点，つまり配列の終点を探す．ここで以下に効率よく絞り込みを行えるかが鍵となる．
安全に，手軽に行くのならば線形検索でよいが，O(N)のオーダであるので配列が小さい時にのみにしか適用すべきではない．
コードは以下の通り．

#include <cstdio>
#include <cstdlib>

int arrVal[] = {1,6,21,25,28,28,31,45,51,53,62,64,85};

int search_linear(int val) {

 int st = 0;
 int mid;
 int end = 0;
 int t;
 while(true) {

  // simulate out of index exception
  try {
   if( end >= (sizeof(arrVal) / sizeof(int)) )
    throw "out of index access";
   t = arrVal[end];
   printf("t=%d,end=%d,val=%d,idx=%d\n",t,end,val,end);
   if( t == val )
    return end;
   else if( t > val )
    break;

  } catch( char* str ) {
   printf("exception:%s.\n", str );
   break;
  }
  end++;
 }

 // now we know the end index of the "unbounded array.". Do the bsearch!
 while( st <= end ) {
  mid = (st + end) / 2;
  printf("st=%d,end=%d,mid=%d,val=%d,midval=%d\n",st,end,mid,val,arrVal[mid]);
  if( arrVal[mid] == val)
   return mid;
  else if( arrVal[mid] > val )
   end = mid - 1;
  else
   st = mid + 1;
 }
 return -1;

}


int main() {

 printf("%d ? %d\n",64,search(64));
 printf("%d ? %d\n",25,search(25));
 printf("%d ? %d\n",6,search(6));
 printf("%d ? %d\n",19,search(19));
 printf("%d ? %d\n",53,search(53));
 printf("%d ? %d\n",85,search(85));
 return EXIT_SUCCESS;
}

データが大きくなった場合，どうするか？上のコードでは計算量が多くて話にならないので，
なんとかlog2Nのオーダで絞り込むことを考える．
例外が投げられるか，又はA[2^k-1]の値が検索対象の値より大きくなるかのどちらかを満たすまで配列の終点と推定できるインデックスを探す．そしてその配列の終点と仮定した点2^k-1と2^kの間でバイナリサーチをすれば，log2Nのオーダの計算量で収まる．