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

Binary Search Algorithm

 

여러가지 탐색 알고리즘들을 보면 여러가지 알고리즘을 찾을 수 있다. 가장 기본적으로는 선형 탐색 방식으로 앞에서 부터 하나씩 비교하며 찾는 방법이다.

 

말그대로 탐색을 한 쪽 끝에서 다른 끝까지 탐색하기 때문에 탐색 대상이 뒤쪽에 위치해있으면서, 탐색 대상이 많은 경우 매우 비효율적일 수 있다. 하지만, 만약 탐색하고자 하는 데이터가 정렬이 되어 있는 경우 좀더 효율 적인 방법을 이용할 수 있는데 이것이 바로 이진 탐색 알고리즘이다.

정의(Definition)

정렬된 탐색대상에서 특정 대상을 찾고자 할때 사용 할 수 있는 탐색 알고리즘

1. 정렬된 알고리즘으로 부터 탐색
2. 중간값과 탐색대상을 비교후 탐색 범위를 절반으로 줄여가며 찾는 알고리즘

이렇게 정렬된 알고리즘으로 부터 해서 중간값과 비교후 작으면 중간값 상위 대상자들은 탐색대상에서 제외하고 클경우는 하위 대상을 탐색대상에서 제외하는 알고리즘이다.

 

여기서 결국 탐색 범위를 확인해야하기 때문에 투포인터(two-pointer)를 활요해 주어야 한다.

어떻게 진행될까?

위 진행과정을 보면 반복적으로 중간점을 비교해 가는것을 알 수 있다.

1. 첫 번째 비교 후 0~2 인덱스는 탐색 대상에서 제외
2. 2번째 중앙값 비교 후 하위 대상 탐색대상 제외
3. 3번째 중앙값 비교시 타겟과 일치함.

즉, 중앙값이 찾는 대상과 일치할때 까지 반복해서 범위를 줄여나가면 된다.

소스코드

해당 알고리즘 또한 반복문 혹은 재귀를 이용하여 구현할 수 있다.

재귀로 구현 시

int Binary_Search_Recursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return Binary_Search_Recursive(arr, target, low, mid-1);
    else
        return Binary_Search_Recursive(arr, target, mid+1, high);
}

반복문으로 구현 시

int Binary_Search(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

Source.cpp

0.00MB