[자료구조와 알고리즘] 이진 검색

이진 검색(Binary Search) 은 정렬된 배열에서 원하는 값을 찾을 때, 중앙 값을 기준으로 탐색 범위를 반으로 줄여가며 찾는 효율적인 알고리즘입니다.

• 배열이 오름차순(또는 내림차순)으로 정렬되어 있어야 사용할 수 있음.
• 배열의 중앙 값과 찾고자 하는 값을 비교하여 왼쪽 또는 오른쪽 반만 검색함.
• 매 단계마다 검색 범위가 절반으로 줄어들므로 시간 복잡도는 O(log n) 으로 매우 빠름.

(1) 반복문을 이용한 이진 검색

public class BinarySearch {
    // 반복문을 이용한 이진 검색
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2; // 중간 값

            if (arr[mid] == target) {
                return mid; // 값 찾음
            } else if (arr[mid] < target) {
                low = mid + 1; // 오른쪽 반 탐색
            } else {
                high = mid - 1; // 왼쪽 반 탐색
            }
        }
        return -1; // 값을 찾지 못한 경우
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13}; // 정렬된 배열
        int target = 7;

        int index = binarySearch(arr, target);

        if (index != -1) {
            System.out.println("값 " + target + "은(는) 인덱스 " + index + "에 있습니다.");
        } else {
            System.out.println("값 " + target + "을(를) 찾을 수 없습니다.");
        }
    }
}

(2) 재귀(Recursive) 방식의 이진 검색

public class BinarySearchRecursive {
    // 재귀 호출을 이용한 이진 검색
    public static int binarySearchRecursive(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 binarySearchRecursive(arr, target, mid + 1, high); // 오른쪽 탐색
        } else {
            return binarySearchRecursive(arr, target, low, mid - 1); // 왼쪽 탐색
        }
    }

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

        int index = binarySearchRecursive(arr, target, 0, arr.length - 1);

        if (index != -1) {
            System.out.println("값 " + target + "은(는) 인덱스 " + index + "에 있습니다.");
        } else {
            System.out.println("값 " + target + "을(를) 찾을 수 없습니다.");
        }
    }
}

6. 결론

• 이진 검색은 O(log n)의 빠른 검색 속도를 가지므로 데이터가 많을수록 유리
• 단, 정렬된 배열에서만 사용할 수 있으며, 정렬이 필요하다면 추가적인 시간 복잡도가 발생
• 작은 데이터셋에서는 선형 검색이 더 쉬울 수 있지만, 큰 데이터에서는 이진 검색이 훨씬 효율적