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

[개념]

 

이진 탐색은 데이터가 정렬되어 있는 상태에서 특정 데이터를 찾는다.

배열의 시작, 중간, 끝 index를 조절해가며 탐색을 한다.

찾고자 하는 값인 x가 배열의 중간 값보다 작으면 중간을 기준으로 왼쪽에 있는 데이터 중에서만 찾고

x가 배열의 중간 값보다 클 경우 중간을 기준으로 오른쪽에 있는 데이터 중에서만 찾는다.

 

이와 같이 탐색 범위를 좁혀가면서 찾고자하는 값을 찾아낸다.

 

 

 

 

위의 그림은 이진 탐색의 예시로 정렬된 배열을 가지고 시작한다.

찾고자 하는 값인 13은 처음 mid인 7보다 크므로 

low = mid +1이 되고 , mid = (low+high)/2 = 3 이 된다.

arr[3]이 13이므로 true를 반환하면서 탐색을 종료한다.

 

 

[코드]

 

 

아래 코드와 같이 low는 배열의 시작, high는 배열의 끝 index부터해서

중간 값인 mid보다 찾고자하는 값인 target이 더 크면 low값을 mid+1 로 update 하고

target 값이 더 작은 경우 high의 값은 mid-1로 update 하여 탐색하는 범위를 좁혀 나갈 수 있다.

 

bool BinarySearch()
{
    int mid;
    int low =0;
    int high = N-1;
    
    while(low <= high)
    {
        mid = (low + high)/2;
        if(arr[mid] == target)  return true;
        else if(arr[mid] < target)  low = mid +1;
        else    high= mid-1;
    }
    return false;
}