[알고리즘] 탐색 알고리즘 기본적인 이해와 구현 - 2. 이진 탐색

1. 선형 탐색 (Linear Search)
2. 이진 탐색 (Binary Search)
3. 점프 탐색 (Jump Search)
4. 보간 탐색 (Interpolation Search)
5. 지수 탐색 (Exponential Search)
6. 깊이 우선 탐색 (Depth-First Search, DFS)
7. 너비 우선 탐색 (Breadth-First Search, BFS)

 

 

이진 탐색

이진 탐색은 정렬된 배열이나 리스트에서 원하는 값을 효율적으로 찾기 위해 사용하는 알고리즘입니다. 배열을 절반씩 나누어 탐색 대상을 좁혀가며 빠르게 원하는 값을 찾을 수 있으며, 특히 대규모 데이터셋에서 유용합니다.

 

1. 특징

• 분할 정복 방식: 탐색 범위를 계속해서 절반으로 줄여 나가는 방식입니다. 매번 중간 값을 기준으로 탐색 범위를 좁혀가므로 탐색 속도가 빠릅니다.
• 정렬된 데이터 필요: 이진 탐색은 데이터가 오름차순 또는 내림차순으로 정렬된 상태에서만 사용할 수 있습니다. 정렬되지 않은 데이터의 경우 먼저 정렬 작업이 필요합니다.
• 효율성: 데이터 양이 증가할수록 선형 탐색보다 훨씬 빠른 속도를 자랑합니다.

 

2. 복잡도

• 시간 복잡도: 평균 및 최악의 경우 모두 O(log n)으로, 데이터의 크기가 커질수록 로그 형태로 시간이 증가합니다. 예를 들어, 1,000개의 데이터가 있을 때 최대 10번, 1,000,000개의 데이터에서는 최대 20번 정도의 비교로 값을 찾을 수 있습니다.
• 공간 복잡도: O(1)로, 추가적인 메모리 공간을 거의 필요로 하지 않습니다. 단, 재귀적으로 구현할 경우 스택 공간을 사용할 수 있습니다.

 

3. 예제

public class BinarySearchExample {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid; // 값을 찾은 경우 인덱스 반환
            }

            if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 절반에서 탐색
            } else {
                right = mid - 1; // 왼쪽 절반에서 탐색
            }
        }

        return -1; // 값을 찾지 못한 경우 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 7;
        int result = binarySearch(arr, target);

        if (result == -1) {
            System.out.println("원소를 찾을 수 없습니다.");
        } else {
            System.out.println("원소는 인덱스 " + result + "에 위치해 있습니다.");
        }
    }
}

• 이 코드에서는 정렬된 배열 arr에서 중간 인덱스를 기준으로 원하는 값 target을 찾기 위해 반복적으로 왼쪽과 오른쪽 범위를 줄여 나갑니다. 값을 찾으면 해당 인덱스를 반환하고, 없으면 -1을 반환합니다.

 

4. 주 사용처

• 대규모 데이터셋: 이진 탐색은 데이터가 많을 때 효율적이며, 데이터가 클수록 탐색 속도의 이점이 커집니다.
• 정렬된 목록: 정렬된 데이터에서 특정 값이나 객체를 빠르게 찾을 때 사용됩니다.
• 검색 기능: 주로 DB 검색, 파일 탐색, 데이터 분석 등 다양한 검색 기능에 사용됩니다.

 

감사합니다.