이진 검색

CString CAutoDicDlg::SearchDic( CString strResult )
{
 // TODO: Add your control notification handler code here

 CString strDic, strParam;
 BOOL bUp = TRUE;
 int nCurrentPos=0, nFirstPos, nLastPos, nBeforePos;
 int nCount, nKeyLength, nTokenLength, nSearchCnt, nGap;

 TCHAR *buf, *token, *keyword, *keyhead;
 const TCHAR sep[] = _T("/");

 strParam = strResult;
 keyword = strParam.GetBuffer(1024+1);
 nKeyLength = lstrlen(keyword);
 keyhead = keyword;
 
 nSearchCnt = 0;
 nFirstPos = 0;
 nLastPos = m_nTotalLine;
 
 while( 1 )
 {
  nBeforePos = nCurrentPos;
 
  nGap = (nLastPos - nFirstPos)%2 == 1 ? (nLastPos - nFirstPos)/2 + 1: (nLastPos - nFirstPos)/2;
  if( bUp )
   nCurrentPos = nCurrentPos + nGap;
  else
   nCurrentPos = nCurrentPos - nGap;
 
  if( nBeforePos == nCurrentPos )
   break;

  if( nSearchCnt > 20 )
   return strResult;
   
  nSearchCnt++;         // 라인 검색 횟수

  CString strTemp = m_arrDic.GetAt( nCurrentPos );
  buf = (LPTSTR)strTemp.GetBuffer(1024+1);
  token = _tcstok(buf, sep);
   
  nCount = 0;
  nTokenLength = lstrlen(token);
  keyword = keyhead;
 
  while( *keyword != NULL && *token != NULL )
  {
   // 대문자 -> 소문자 전환
   if( *keyword >= 65 && *keyword <= 90 )    *keyword += 32;
   if( *token >= 65 && *token <= 90 )      *token += 32;

   if( *keyword == *token )
   {
    nCount++;
    keyword++;
    token++;

    if( *token == NULL )   // 검색어가 피검색어를 포함할 때
    {
     bUp = FALSE;
     nLastPos = nCurrentPos;
     break;
    }
    continue;
   }
   else if( *keyword < *token )
   {
    bUp = FALSE;
    nLastPos = nCurrentPos;
    break;
   }
   else if( *keyword > *token )
   {
    bUp = TRUE;
    nFirstPos = nCurrentPos;
    break;
   }
  }
 
  if( nKeyLength == nCount )
  {
   if( nKeyLength == nTokenLength )   // 검색어가 피검색자와 같을 경우
   {
    return m_arrDic.GetAt( nCurrentPos );
   }
   else              // 검색어가 피검색자에 포함될 경우 
   {
    bUp = FALSE;
    nLastPos = nCurrentPos;
   }
  }
 }

 return strResult;
}

STL에 삽입된 12만 라인 정도의 사전 데이터에서 일치하는 단어를 찾는 이진검색
이진검색의 힘~ㅎ 12만라인에서 최대 검색횟수가 17번 정도이다. ㅡㅡ;;;