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

問題．


Write a method that takes a sorted array A of integers and a key k and
returns the index of first occurrence of k in A. Return -1 if k does not
appear in A. 
(出典: Algorithm for interviews )

これは，ただ単に２分検索．あまりに捻りがないので逆に疑って問題を読んでしまった．

解．


#include <stdio.h>
#include <stdlib.h>

static int intArray[] = {2,16,18,18,21,35,42,59,60,68,74,92};

int bsearch(int k) {

int st,end,mid;
st = 0;end = sizeof(intArray)/sizeof(int)-1;

while(st <= end) {
mid = (st+end)/2;
printf("st-%d,end-%d,mid-%d,k-%d,midVal=%d\n",st,end,mid,k,intArray[mid]);
if(intArray[mid] == k)
return mid;
else if(intArray[mid] < k)
st = mid + 1;
else
end = mid - 1;
}
return -1;
}

void show_result(int num, int result){
printf("%d:%d\n", num, result);
}

int main(int argc, char **argv) {
// not found
show_result(68,bsearch(68));
// found
show_result(74,bsearch(74));
char ch;
scanf(&ch);
return EXIT_SUCCESS;
}


特に捻りもなく，実に普通のbsearchである．
アウトプットは以下の通り．bsearchを書くといつも義経の八艘飛びを思い浮かべるのは私だけだろうか．

st-0,end-11,mid-5,k-68,midVal=35
st-6,end-11,mid-8,k-68,midVal=60
st-9,end-11,mid-10,k-68,midVal=74
st-9,end-9,mid-9,k-68,midVal=68
68:9
st-0,end-11,mid-5,k-74,midVal=35
st-6,end-11,mid-8,k-74,midVal=60
st-9,end-11,mid-10,k-74,midVal=74
74:10

平均オーダはO(log2 n)．最悪でもO(log2 n)．線形サーチはO(n)なのでソートするコスト(例えば n log n ) を合わせても十分見合うことがわかる．