Algorithm 問題を解く3 - バイナリサーチ(２分探索) その弐

問題

SEARCH A SORTED ARRAY FOR A[i] = i

Suppose that in addition to being sorted, the entries of A are distinct integers. Design an efficient algorithm for finding an index i such that A[i] = i or indicating that no such index exists.

( 出典: algorithms for interviews )

ヒント

sorted arrayときたらまずとりあえず考えるのは? 
distinct integers, つまり重複無しのソート済み配列である．

答え

重複無しのソート済み配列とのこと．昇順であると仮定すれば以下が成り立つ

S[i] > S[i-1]

私の解答は以下の通り．
ロジックとはしては調べたいインデックスを２分木で絞り込む．調べたい値targetと２分木の中央要素v.at(mid)が等価ならばそのインデックスを返し，２分木探索終了時まで見つからなければ問題の指示通り-1を返す．

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

#define INTARRAY_MAX 10

int search(vector<pair<int,int>> v, int target) {
 
 int st = 0;
 int end = v.size() - 1;
 int mid;
 while( st < end ) {
  
  mid = (st + end) / 2;
  cout << st << ',' << end << ',' << mid << ',' << v.at(mid).second << endl;
  if( v.at(mid).second == target )
   return mid;
  else if( v.at(mid).second > target )
   end = mid - 1;
  else
   st = mid + 1;
 }
   
 return -1;
}

int main() {
 vector<pair<int,int>> v;
 int arrVal[] = { 0,1,3,15,18,26,38,45,50,62};
 for( int i = 0;i < INTARRAY_MAX;i++ )
  v.push_back(make_pair(i,  arrVal[i] ));

 cout << "find? " << search(v, 1) << endl;
 cout << "find? " << search(v, 5) << endl;

 return EXIT_SUCCESS;
}

プログラムを走らせると以下のようなアウトプットを得る．

0,9,4,18
0,3,1,1
find? 1
0,9,4,18
0,3,1,1
2,3,2,3
find? -1

O(log2N)の平均又は最悪計算量で終えることできるのでデータ量が多くても大丈夫．(最もここではソートのコストは考慮に入れていない．)
ちなみにutilityヘッダはSTLのpairを使用する為に必要．