[ 자료구조 ] 탐색 - 02 . 이진탐색

[이진 탐색]

[이진 탐색]

이진 탐색은 정렬된 데이터 집합에서 사용할 수 있는 '고속'탐색 알고리즘이다 .

이진 탐색이라는 이름은 알고리즘의 핵심이 탐색범위를 1/2 씩 줄여나가는 방식에 있기 때문에 붙여졌다 .

 

[과정]

• 데이터 집합의 중앙에 있는 요소를 고른다 .
• 중앙요소의 값과 찾고자 하는 목표값을 비교한다
• 목표값과 중앙요소의 값을 비교해 목표값이 중앙요소가 작다면 왼편,크다면 오른편에 대한 이진검색을 수행한다
• 찾고자 하는 값을 찾을때까지 위의 과정을 반복한다 .

[성능]

이진 탐색은 참색을 시도할때마다 탐색의 범위가 1/2씩 줄어들어 결국은 1이 된다 . 1의 경우 (마지막 데이터 범위)를 

식으로 나타내자면 1 = n * (1/2)x제곱이며 이를 단순화 한다면 x = log2n으로 나타낼수 있다 .

=>이는 데이터 집합의 크기가 아무리 크더라도 탐색 소요 시간은 미미하게 증가함을 나타낸다

ex)100만개는 20회 , 1000만개는 23회의 탐색을 반복하면 찾을 수 있다 .

 

[ 구현 ]

구현은 다음과 같다 .

ElementType BinarySearch(ElementType DataSet[] , int size , ElementType Target)
{
	int Left = 0;
    int Right = size-1;
    int Mid=0;
    
    //탐색 범위가 0이 될때 까지
    while(Left <= Right)
    {
    	Mid = (Left+Right)/2;
        if(Target == DataSet[Mid]
        	return DataSet[Mid]
        else if(Target>DataSet[Mid]
        	Left=Mid+1;
        else
    		Right=Mid-1;
    }
    return NULL;
}

 

[ c 표준 라이브러리의 이진 탐색 함수 : bserch()]

[bsearch]

표준 라이브러리가 퀵 정렬을 구현한것과 같이 이진 탐색을 구현한 bsarch()도 존재한다 .

원형은 다음과 같다 .

void * bsearch
{
	const void *key,	//찾고자 하는 목표값 데이터의 주소
    const void *base,	//데이터 집합 배열의 주소
    size_t num,			//데이터 요소의 개수
    size_t width,		//한 데이터 요소의 크기
    int (__cdecl *compare)(const void* , const void*)//비교 함수에 대한 포인터
};