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

C | C++ | VC++

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

두루물 2010. 12. 23. 15:54

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

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

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

저작자표시 (새창열림)