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

이진 탐색(Binary Search)

---

이진 탐색은 정렬된 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

시간 복잡도는 O(logN)으로 빠른 시간 복잡도를 가진다.

이진 탐색 알고리즘을 적용하기 위해서는 데이터가 정렬되어 있어야 하고 데이터 구조의 모든 요소에 액세스 하려면 일정한 시간이 걸리게 된다.

 

이진 탐색 과정(오름차순 기준)

1. 현재 데이터셋의 중앙값을 선택한다.

중앙값 선택

 

2. 중앙값과 타깃 데이터를 비교하여 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.

현재 타깃 데이터는 50, 중앙값은 37로 서로 비교해보면 타깃 데이터가 더 크기 때문에 왼쪽 데이터셋은 선택하지 않는다.

 

3. 중앙값과 타깃 데이터를 비교하여 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.

오른쪽 데이터셋 선택

타깃 데이터와 중앙값을 비교해보면 타깃 데이터가 더 크기 때문에 오른쪽 데이터 셋을 선택한다.

 

4. 과정 1 ~ 3번을 반복하다가 중앙값과 타깃 데이터가 같아지면 탐색을 종료한다.

결과 확인

위의 과정을 반복해서 타깃값을 찾는다.

이진 탐색을 사용하면 N개의 데이터에서 log(N) 번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.

위의 예시를 보면 16개의 데이터에서 log(16) 즉, 4번의 연산으로 원하는 데이터를 찾을 수 있다.

 

코드로 보는 이진 탐색

public class Binary_Search {
    public static int binarySearch(int[] arr, int low, int high, int target) {
        if (high >= low) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return mid;
            }

            if (arr[mid] > target) {
                return binarySearch(arr, low, mid - 1, target);
            }

            return binarySearch(arr, mid + 1, high, target);
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 5, 14, 18, 24, 29, 31, 37, 45, 49, 50, 56, 63, 68, 72, 77};
        int target = 50;
        int result = binarySearch(arr, 0, arr.length - 1, target);
        System.out.println(result);
    }
}

 

이진 탐색의 장단점

이진 탐색의 장점

이진 탐색은 시간 복잡도가 최악의 경우에도 logN으로 다른 선형 탐색보다 상당히 빠른 성능을 보여주기 때문에 대규모 배열에서 사용하기 적합하다.

하드 드라이브나 클라우드와 같은 외부 메모리에 저장된 대규모 데이터 세트를 검색하는 데 매우 적합하다.

 

이진 탐색의 단점

이진 탐색을 하기 위해서는 배열이 오름차순 혹은 내림차순으로 정렬되어야 한다. 정렬되지 않으면 잘못된 결과를 반환할 수 있다.

이진 탐색을 위해서는 데이터 구조가 연속적인 메모리 위치에 저장되어 있어야 한다. 메모리에 연속적인 위치라는 것은 배열을 의미하는 것으로 배열에 저장되어 있는 데이터를 탐색할 때 유용하다.

이진 탐색에서는 배열 요소가 비교 가능해야 한다. 즉, 순서를 지정할 수 있어야 한다. 순서를 지정할 수만 있다면 숫자 데이터 외에도 알파벳 같은 문자도 이진 탐색을 할 수 있다.