2분법을 이용한 이진탐색(Binary Search) 샘플코드

binarysearch.7z

이미 순차정렬된 레코드 배열에서 특정값을 찾기위한 탐색알고리즘으로는 여러가지가 있는데 그중 중간값으로 2분하여 탐색하는 이진탐색은 비교적 적은 코드로 단순한 for 문으로 하는 순차탐색 보다 탁월한 O(log2N)의 탐색시간을 자랑한다.
특히,배열이나 레코드 등 내부에서 관리하는 리스트가 대용량일때 빛을 발한다.

// binarysearch.cpp : O(log2N)의 탐색 평균속도를 내는 2진탐색 샘플 // http://krkim.net #include "stdafx.h" #include "windows.h" struct MYDATA{  int pos;  int style; }; int binarysearch(int *arraylist,int arraysize,int findvalue); int binarysearchprev(MYDATA *arraylist,int arraysize,int findvalue,int findstyle); int _tmain(int argc, _TCHAR* argv[]) {  int arraylist[]={10,12,13,15,18,27,39,100,101,113,215,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};  int arraylist2[]={-1,-1,-1};  MYDATA mylist[] = { {10,1},{15,1},{17,1},{110,1},{120,2},{129,1},{2100,1},{-1,1},{-1,1},{-1,1}};  //binarysearch(arraylist,ARRAYSIZE(arraylist),15);  binarysearchprev(mylist,ARRAYSIZE(mylist),2000,2);  return 0; } int binarysearch(int *arraylist,int arraysize,int findvalue) {  int lo = 0;  int hi = arraysize - 1;  int cp;  int loop = 0;  int dummyvalue = -1; // while(hi > 0 && arraylist[hi] == -1) hi--;  for(;;){   loop++;   cp = (lo + hi) / 2;      if(findvalue == arraylist[cp]){    break;   }   if(lo >= hi)    break;   if(arraylist[cp] == dummyvalue)//뒷부분이 dummy로 채워져 있음    hi = cp - 1;   else if(findvalue > arraylist[cp]){    lo = cp + 1;    //같은값이 없으면 항상 크거나 작은 값 둘중 어느하나가 불규칙하게 탐색된다.    //이유는,배열의 데이타 갯수 여부의 홀짝에 따라 중간값이 달라지기 때문이다.    //따라서,같은값이 없을때 작은값을 구하기 위해 비교한다.    //같은값만 찾으려면 아래는 필요없음.또는 데이타의 끝에 dummy 값을 만나도 멈춤    //같은값이 없으면 작은값중 최대값으로 찾고 뒷부분의 더미바이트를 만나면 멈춘다.    if(findvalue < arraylist[lo] || arraylist[lo] == dummyvalue){     break;    }   }   else    hi = cp - 1;  }  char msg[300];  sprintf(msg,"loop[%d] findvalue = %d => array[%d] = %d\r\n",loop,findvalue,cp,arraylist[cp]);  OutputDebugStr(msg);  return 0; } //findvalue보다 pos가 작거나같고 style이 findstyle 과 다른 항목 찾기 int binarysearchprev(MYDATA *arraylist,int arraysize,int findvalue,int findstyle) {  int lo = 0;  int hi = arraysize - 1;  int cp;  int loop = 0;  int dummyvalue = -1;  // while(hi > 0 && arraylist[hi] == -1) hi--;  for(;;){   loop++;   cp = (lo + hi) / 2;   if(findvalue == arraylist[cp].pos)    break;   if(lo >= hi)    break;   if(arraylist[cp].pos == dummyvalue)//뒷부분이 dummy로 채워져 있음    hi = cp - 1;   else if(findvalue > arraylist[cp].pos){    lo = cp + 1;    if(findvalue < arraylist[lo].pos || arraylist[lo].pos == dummyvalue){     break;    }   }   else    hi = cp - 1;  }  int loop2 = 0;  int findpos = -1;  for(int pos = cp; findpos == -1 && pos >= 0 ; pos--){   loop2++;   if(arraylist[pos].pos <= findvalue && arraylist[pos].style != findstyle)    findpos = pos;  }  char msg[300];  if(findpos != -1){   cp = findpos;   sprintf(msg,"loop[%d] loop2[%d] findvalue = (%d,%d) => array[%d] = (%d,%d)\r\n",    loop,loop2,findvalue,findstyle,cp,arraylist[cp].pos,arraylist[cp].style);   OutputDebugStr(msg);  }  else{   sprintf(msg,"loop[%d] loop2[%d] findvalue = (%d,%d) => not found in this list\r\n",    loop,loop2,findvalue,findstyle);   OutputDebugStr(msg);  }  return 0; }