[자료구조] 이진탐색(Binary Search)

이진탐색(Binary Search)

이진탐색이란 `정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘`이다. 탐색 범위를 절반씩 줄이며 찾는 값이 포함된 범위를 좁혀간다. 선형탐색보다 빠른 속도를 보장하지만 배열이 정렬되어 있어야지만 한다.

 

1. 이진탐색 과정

이진 탐색은 중간값이 타겟값보다 크면 왼쪽, 작으면 오른쪽을 탐색한다.

 

1. 배열의 **중간값(mid)**을 기준으로 타겟값과 비교한다.

2. 중간값이 타겟값보다 크면, 탐색 범위를 왼쪽 절반으로 줄인다.

3. 중간값이 타겟값보다 작으면, 탐색 범위를 오른쪽 절반으로 줄인다.

4. 이 과정을 반복하며 탐색 범위를 좁혀 나간다.

 

 

이진 탐색이 선형 탐색의 차이점

이진 탐색에 대한 코딩테스트 문제의 예제를 보면 선형 탐색이 더 나아보이는 예제들이 있다. 그래서 선형 탐색으로 진행해보면 시간초과가 발생하게 된다.

- 선형 탐색의 경우 단순 for문을 이용하기 때문에 어떤 경우 빠르게 찾을 수 있지만 나쁜 경우에 모든 루프를 다 돌아야 한다. - 이진 탐색의 경우 정렬된 배열에서 중간값을 찾아 탐색 범위를 반으로 줄여 값을 찾으므로 속도상 이점이 있다.

 

2. 구현코드(Java)

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) // 타켓값을 찾는경우 
                return mid;
            else if (arr[mid] < target) // 중간값이 타겟보다 작다면 값이 오른쪽에 있다는 말
                left = mid + 1;
            else   // 중간값이 타겟보다 크다면 값이 왼쪽에 있다는 말
                right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 5;
        int result = binarySearch(data, target);
        System.out.println("이분 탐색 결과: " + result);
    }
}

 

3. 이진 탐색의 성능

이진탐색의 경우 시간 복잡도를 확인하였을때 로그 시간인 `O(logn)`으로써 다른 정렬에 비해 상대적으로 매우 빠르다.