[알고리즘] 이진 탐색(Binary Search) 개념 및 구현

[알고리즘] 이진 탐색(Binary Search) 개념 및 구현

📌 이진 탐색(Binary Search)이란?

이진 탐색은 정렬된 배열에서 **탐색 범위를 반씩 줄여가며 값을 찾는 알고리즘**입니다.
탐색할 데이터가 많을 경우, **선형 탐색(순차 탐색)보다 훨씬 빠르게 원하는 값을 찾을 수 있습니다.**

⏳ 시간 복잡도: O(log N) (탐색 범위를 절반씩 줄이므로)

---

📌 이진 탐색 동작 원리

1. 배열의 중간 값을 선택
2. 찾고자 하는 값과 비교
   • 중간 값이 찾는 값보다 크다면 **왼쪽 부분만 탐색**
   • 중간 값이 찾는 값보다 작다면 **오른쪽 부분만 탐색**
   • 중간 값이 찾는 값과 같다면 탐색 종료
3. 위 과정을 반복하여 값을 찾을 때까지 탐색

---

📌 이진 탐색 구현 방법

1️⃣ 반복문을 이용한 이진 탐색

public class BinarySearch {
    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; // 찾은 경우, 해당 인덱스 반환
            } else if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 탐색
            } else {
                right = mid - 1; // 왼쪽 탐색
            }
        }

        return -1; // 찾지 못한 경우
    }

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

        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("값을 찾았습니다! 위치: " + result);
        } else {
            System.out.println("값이 존재하지 않습니다.");
        }
    }
}

---

2️⃣ 재귀 호출을 이용한 이진 탐색

public class RecursiveBinarySearch {
    public static int binarySearchRecursive(int[] arr, int left, int right, int target) {
        if (left > right) return -1; // 종료 조건 (값을 찾지 못한 경우)

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

        if (arr[mid] == target) return mid; // 값을 찾은 경우
        else if (arr[mid] < target) return binarySearchRecursive(arr, mid + 1, right, target); // 오른쪽 탐색
        else return binarySearchRecursive(arr, left, mid - 1, target); // 왼쪽 탐색
    }

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

        int result = binarySearchRecursive(arr, 0, arr.length - 1, target);
        if (result != -1) {
            System.out.println("값을 찾았습니다! 위치: " + result);
        } else {
            System.out.println("값이 존재하지 않습니다.");
        }
    }
}

---

📌 이진 탐색을 사용할 수 있는 경우

• ✅ 정렬된 배열에서 특정 값을 빠르게 찾고 싶을 때
• ✅ 데이터 양이 많을 때 효율적인 탐색이 필요할 때
• ✅ 이진 탐색 기반 알고리즘 (이진 탐색 트리, 삼분 탐색 등)을 활용할 때

---

📌 이진 탐색을 사용할 수 없는 경우

• ❌ 데이터가 정렬되지 않은 경우 (정렬이 필요함)
• ❌ 연속된 데이터가 아닌 경우 (링크드 리스트 등에서는 비효율적)

---

🔍 결론

이진 탐색은 **정렬된 데이터에서 매우 빠르게 값을 찾을 수 있는 알고리즘**으로, 탐색할 데이터가 많을수록 **선형 탐색보다 훨씬 효율적**입니다.

또한, **코딩 테스트 및 면접에서도 자주 등장하는 개념**이므로 꼭 익혀두는 것이 좋습니다! 🚀

---

📌 다른 알고리즘도 궁금하다면 함께 확인하세요!

📌 다른 알고리즘 문제 풀이 보러 가기