[알고리즘] 이진 탐색 설명 및 예제(샘플 소스)

이진 탐색 설명 및 예제

이진 탐색은 정렬된 리스트에서 사용할 수 있는 탐색 알고리즘입니다.

탐색 속도가 빠르다는 장점이 있지만 정렬된 상태에서 사용해야 한다는 제약이 있습니다.

 

이진 탐색의 과정은 다음과 같습니다.

1. 리스트의 중앙에 있는 값을 선택하여 목표 값과 비교합니다.

2. 중앙 값이 목표 값보다 크면 중앙 값의 왼쪽에 대해 이진 탐색을 진행합니다.

3. 중앙 값이 목표 값보다 작으면 중앙 값의 오른쪽에 대해 이진 탐색을 진행합니다.

4. 1~3의 과정을 반복합니다.

 

EX) [1, 2, 3, 4, 5, 6, 7] 이 들어 있는 리스트에서 6을 찾는다고 하면

1. 4을 선택하여 6과 비교합니다.

2. 4는 6보다 작으므로 오른쪽에 있는 [5, 6, 7] 에 대해 이진 탐색을 진행합니다.

3. 중앙 값인 6을 선택하면 찾고자 하는 목표값과 동일하여 탐색을 종료합니다.

 

DataType BinarySearch(DataType dataList[], DataType target, int low, int high)
{
    while (low <= high)
    {
        int mid = (low + high) / 2; // 중앙 값 선택
        if (target == dataList[mid]) // 중앙 값과 목표 값이 동일 -> 탐색 완료
        {
            return dataList[mid];
        }
        else if (target > dataList[mid]) // 목표 값이 중앙 값보다 큼 -> 오른쪽 탐색
        {
            low = mid + 1;
        }
        else // 목표 값이 중앙 값보다 작음 -> 왼쪽 탐색
        {
            high = mid - 1;
        }
    }
    return NULL;
}