이진 탐색(Binary Search)

🔍 이진 탐색(Binary Search) 알고리즘이란?

이진 탐색은 정렬된 데이터에서 원하는 값을 빠르게 찾는 알고리즘입니다. 중간 값을 기준으로 검색 범위를 절반씩 줄여가며 탐색하는 방식입니다.

쉽게 말하면, 전화번호부에서 이름의 첫 글자를 기준으로 책을 반으로 접으며 찾는 방식이에요.

이진 탐색

 

---

✅ 전제 조건

• 데이터가 반드시 정렬되어 있어야 함
  • 오름차순 또는 내림차순 정렬된 상태에서만 사용 가능

---

✅ 작동 방식

예를 들어, 오름차순으로 정렬된 배열 [10, 20, 30, 40, 50, 60, 70] 에서 숫자 50을 찾는 경우:

1. 중간 값: 40 → 찾는 값보다 작으므로 오른쪽 절반 [50, 60, 70]으로 탐색 범위 좁힘
2. 중간 값: 60 → 찾는 값보다 크므로 왼쪽 절반 [50]으로 좁힘
3. 값 50 발견!

👉 이런 식으로 반복적으로 반을 잘라서 찾습니다.

---

📊 시간 복잡도

구분복잡도

최선	O(1)
평균	O(log n)
최악	O(log n)

 

※ 매우 빠름! n개의 데이터도 최대 log₂n번만 비교하면 됨

---

✅ 장점과 단점

✅ 장점

• 검색 속도가 매우 빠름 (대용량 데이터에 적합)
• 구현이 간단하면서도 효율적

❌ 단점

• 정렬된 배열이어야만 사용 가능
• 정렬되지 않은 데이터에는 사용 불가

---

🧪 Java 예제 코드

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) / 2;

            if (arr[mid] == target) {
                return mid; // 찾은 경우
            }

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

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

    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40, 50, 60, 70};
        int target = 50;

        int result = binarySearch(numbers, target);

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

 

---

🖥️ 출력 결과

값 50은 인덱스 4에 있습니다.

 

---

📌 요약 정리

항목설명

알고리즘 이름	이진 탐색 (Binary Search)
필요 조건	정렬된 배열
성능	빠름 (O(log n))
장점	대용량 데이터에도 효율적
단점	정렬 필요, 배열 구조에서만 직접적 적용 가능

 

---

✅ 언제 사용할까?

• 데이터가 이미 정렬되어 있을 때
• 빠른 탐색이 필요한 경우 (ex. 사용자 ID 찾기, 사전 검색 등)
• 대용량 데이터에서 효율적인 검색을 하고 싶을 때