[JAVA] 이분탐색이란?

💻 1. 이분탐색(Binary Search)이란?

이분탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 배열을 반으로 나누어 탐색 범위를 좁혀가며 값을 찾습니다. 그 덕분에 시간 복잡도가 O(log n)으로 매우 빠릅니다.

🔍 1.1 이분탐색의 동작 원리

1. 배열의 중간 값을 확인합니다.
2. 중간 값이 찾고자 하는 값과 같다면 탐색을 종료합니다.
3. 중간 값이 찾고자 하는 값보다 크다면, 배열의 왼쪽 절반을 대상으로 탐색을 계속합니다.
4. 중간 값이 찾고자 하는 값보다 작다면, 배열의 오른쪽 절반을 대상으로 탐색을 계속합니다.
5. 이를 값이 발견되거나 탐색 범위가 더 이상 없을 때까지 반복합니다.

📜 1.2 자바로 구현해보기

이제 자바로 이분탐색을 구현해보겠습니다.

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

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

            if (array[mid] == target) {
                return mid; // 찾았다!
            }

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

        return -1; // 찾지 못함
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 5;
        int result = binarySearch(array, target);

        if (result == -1) {
            System.out.println("원소를 찾지 못했습니다.");
        } else {
            System.out.println("원소를 " + result + " 인덱스에서 찾았습니다.");
        }
    }
}

⚖️ 1.3 이분탐색의 장점과 단점

장점:

• 빠른 탐색 속도: 시간 복잡도가 O(log n)으로 매우 빠릅니다. 큰 데이터셋에서도 효율적입니다.
• 간단한 구현: 코드가 간결하고 이해하기 쉽습니다.

단점:

• 정렬된 배열에서만 작동: 배열이 미리 정렬되어 있어야만 사용할 수 있습니다.
• 삽입과 삭제가 비효율적: 배열이 정렬된 상태를 유지하려면 삽입과 삭제 시 많은 시간이 소요될 수 있습니다.

🏃 1.4 이분탐색과 다른 탐색 알고리즘 비교

순차 탐색(Linear Search)

순차 탐색(Linear Search): O(n)의 시간 복잡도를 가지며, 배열이 정렬되어 있지 않아도 사용 가능합니다. 데이터가 적을 때는 간단하게 사용 가능하지만, 데이터가 많아질수록 비효율적입니다.

순차 탐색을 자바로 구현해보겠습니다.

public class LinearSearch {
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i; // 찾았다!
            }
        }
        return -1; // 찾지 못함
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 5;
        int result = linearSearch(array, target);

        if (result == -1) {
            System.out.println("원소를 찾지 못했습니다.");
        } else {
            System.out.println("원소를 " + result + " 인덱스에서 찾았습니다.");
        }
    }
}

이진 트리 탐색(Binary Tree Search)

이진 트리 탐색(Binary Tree Search): 트리 구조를 이용하여 탐색합니다. 평균적으로 O(log n)의 시간 복잡도를 가지지만, 최악의 경우(비균형 트리) O(n)까지 떨어질 수 있습니다. 삽입과 삭제가 이분탐색보다 효율적일 수 있습니다.

이진 트리 탐색을 자바로 구현해보겠습니다.

class Node {
    int value;
    Node left, right;

    public Node(int value) {
        this.value = value;
        left = right = null;
    }
}

public class BinaryTreeSearch {
    Node root;

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private Node insertRec(Node root, int value) {
        if (root == null) {
            root = new Node(value);
            return root;
        }
        if (value < root.value)
            root.left = insertRec(root.left, value);
        else if (value > root.value)
            root.right = insertRec(root.right, value);

        return root;
    }

    public boolean search(int value) {
        return searchRec(root, value);
    }

    private boolean searchRec(Node root, int value) {
        if (root == null) {
            return false;
        }
        if (root.value == value) {
            return true;
        }
        return value < root.value ? searchRec(root.left, value) : searchRec(root.right, value);
    }

    public static void main(String[] args) {
        BinaryTreeSearch tree = new BinaryTreeSearch();

        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        for (int value : array) {
            tree.insert(value);
        }

        int target = 5;
        if (tree.search(target)) {
            System.out.println("원소를 찾았습니다.");
        } else {
            System.out.println("원소를 찾지 못했습니다.");
        }
    }
}

---

📝 요약

이분탐색은 정렬된 배열에서 빠르게 값을 찾을 수 있는 효율적인 알고리즘입니다. 시간 복잡도 O(log n)으로 매우 빠르고, 구현도 간단합니다. 하지만 정렬된 배열에서만 사용할 수 있고, 삽입과 삭제가 비효율적이라는 단점도 있습니다. 순차 탐색과 이진 트리 탐색 등 다른 탐색 알고리즘들과 비교해보면서 상황에 맞게 사용하는 것이 중요합니다.