[ 알고리즘] 이분탐색(Binary Search)

[개념]

 

이분탐색이란 탐색기법중 하나로 중간값을 기준으로 탐색 범위를 절반씩 줄여가며  탐색한다.

 

따라서 처음부터 끝까지 모두 탐색하는 기법은 worst case의 경우 시간복잡도가 (O(N))이다.

하지만 이분탐색의 경우 탐색범위를 절반씩 줄여나가기 때문에 O(logN)으로 완전탐색보다 빠르다.

 

1. 탐색하고자 하는 배열은 이미 정렬이 되어있다.

2. left, right 값을 통해 중간값인 mid 값을 구한다.

3-1. 찾고자하는 값이 mid 위치에 존재하는 값보다 클 경우 , left를 mid 뒤로 옮긴다.

3-2. 찾고자하는 값이 mid 위치에 존재하는 값보다 작을 경우 , right를 mid 앞으로 옮긴다.

4. 다시 위의 과정을 left가 right 값보다 커질 때까지 반복한다. 

 

 

- 예시

배열의 총 길이는 8이므로 

left =0 , right= 7이되고 mid=3가 된다.

 

 

mid에 존재하는 값이 찾고자 하는 값인 7보다 크므로 right를 mid-1로 update 한다.

이 때 , mid에 존재하는 값보다 찾고자 하는 값인 7이 더 뒤에 있으므로 left를 mid+1로 update 한다.

 

 

마지막으로 left,right,mid 모두 같은 위치에 존재하고 드디어 찾고자 하는 7을 찾을 수 있게 되었다.

 

 

[코드]

 

int main(void)
{
    int arr[8]  = {1,3,7,8,9,15,17,21};
    
    int target = 7;
    int left = 0;
    int right = 7;
    int mid;
    
    while(left <= right)
    {
        mid = (left+right)/2;
        if(arr[mid] < target )  left = mid+1;
        else if( arr[mid] > target) right = mid-1;
        else    return mid;
    }
}