이분 탐색이란(Binary Search)?

이분 탐색은 이진 탐색, Binary Search라고도 하며 모든 경우의 수를 도는 순차적 탐색보다

더 빠른 탐색을 위해 나온 방법이다.

순차적 탐색

말 그대로 순차적으로 건너뛰는 일 없이 0부터 탐색하는 것이다.

출처 : 글쓴이

 

이분 탐색

이분 탐색에서 중요한 것은 정렬이 되어있어야 한다.

정렬되어 있지 않으면 탐색이 불가능하기 때문에 필수 조건이다.

 

mid = (left + right) / 2

만약 크다면 left = mid + 1

만약 작다면 right = mid -1

1. 찾으려는 특정 원소와 시작점, 끝점을 찾아 중간 점을 구한다.
2. 찾으려는 원소의 값이 중간 점보다 작다면 시작점은 유지, 끝점은 중간점에서 -1 하여 바꿔주고 중간점을 구한다.
   만약 크다면 반대로 시작점을 중간점 +1로 변경, 끝점 유지하여 중간 점을 다시 구해준다.
3. 찾을 때 까지 반복한다.

출처 : 글쓴이

 

중간 점을 지정할 때 소수가 나오는 경우가 있는데 그럴 경우에는 버려준다.

ex) 1.5 -> 1

 

 

 

이분 탐색 구현(Java)

이분 탐색은 두 가지 방법으로 구현이 가능하다.

 

1. 반복문

public static boolean BSearch(int[] arr, int n) {
    int left = 0;
    int right = arr.length - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;
        if (arr[mid] < n) left = mid + 1;
        else if (arr[mid] > n) right = mid - 1;
        else return true;
    }
    return false;
}

 

 

2. 재귀호출

public static boolean BSearchRecursive(int[] arr, int n, int left, int right) {
    if(left > right) return false;

    int mid = (left + right) / 2;

    if (arr[mid] < n) 
        return BSearchRecursive(arr, n, mid +1, right);
    else if (arr[mid] > n) 
        return BSearchRecursive(arr, n, left, mid - 1);
    else 
        return true;

}

 

 

시간 복잡도

탐색 기법	시간 복잡도
순차적 탐색 이분 탐색	O(n) O(log n)

 

운이 정말정말 좋다면 순차적 탐색으로 한 번에 찾을 수 있겠지만 이건 운에 기대는 행위라서 최악의 경우를 생각해본다면 잘 사용하지 않는다.

예를 들어 10억 명이 정렬된 배열에서 이진 탐색을 이용해 특정 이름을 찾는다면
단 30번의 비교만으로 검색이 완료된다.
하지만 순차 탐색의 경우 평균 5억 번의 비교가 있어야 된다.