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

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

duruedit 소스코드에서 발췌.샘플

binarysearch.zip

0.77MB

 

binarysearch.7z

0.01MB

 

// 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; }

 

추가

// binarysearch.cpp : O(log2N)의 탐색 평균속도를 내는 2진탐색 샘플 // 이미 순차적으로소팅된 배열에서 같은값,유사값 찾기 // http://krkim.net //2010년 두루에디트 문자열 검색에서 발췌 durumul@gmail.com //20250213 호가창에서 같은가격 10호가중에서 찾기로 활용 #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}}; int pos1 = 0; int pos2 = 0; pos1 = binarysearch(arraylist,ARRAYSIZE(arraylist),15); pos2 = binarysearchprev(mylist,ARRAYSIZE(mylist),2100,2); printf("이진탐색으로 빠른시간에 원하는 값 찾기(탐색속도:O(log2N) 현존 알고리즘에서 개빠름)\n"); printf("http://durumul.com ==========================================================\n\n"); printf("문제1) 다음배열에서 15값 찾기\n"); printf("int arraylist[]={10,12,13,15,18,27,39,100,101,113,215,\n"    "                 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};\n"); printf("문제2) 다음 구조체 배열에서 2100보다 같거나 작은값 찾기\n"); printf("MYDATA mylist[] = { {10,1},{15,1},{17,1},{110,1},{120,2},{129,1},{2100,1},{-1,1},{-1,1},{-1,1}};\n"); printf("\n과연 정답은?(인덱스 0부터 시작\n"); system("pause"); printf("binarysearch(일치하는값) 찾은위치:pos1=%d\n", pos1); printf("binarysearchprev(작거나같은값) 찾은위치:pos=%d\n",pos2); getchar();//아무키나 입력대기 printf("안녕히~~\n"); 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; int findpos = -1; // while(hi > 0 && arraylist[hi] == -1) hi--; for(;;){ loop++; cp = (lo + hi) / 2; if(findvalue == arraylist[cp]){//찾음 findpos = 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]); OutputDebugString(msg); return findpos; } //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); OutputDebugString(msg); } else{ sprintf(msg,"loop[%d] loop2[%d] findvalue = (%d,%d) => not found in this list\r\n", loop,loop2,findvalue,findstyle); OutputDebugString(msg); } return findpos; }