Java에서 이진 검색을 위한 프로그램 쉽게 이해하기

이진 검색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘입니다. 이 알고리즘은 "반씩 나누며 찾기" 방식을 사용해서 검색 속도를 높이는 것이 특징입니다. 

---

이진 검색의 기본 개념

1. 배열이 오름차순으로 정렬되어 있어야 합니다.
2. 검색하려는 값(target)과 배열의 중간 값을 비교합니다.
3. 비교 결과에 따라 검색 범위를 절반으로 줄입니다.
   • 중간 값이 target보다 크다면 왼쪽 절반을 검색합니다.
   • 중간 값이 target보다 작다면 오른쪽 절반을 검색합니다.
4. 이를 반복하다 보면 값을 찾거나, 범위가 더 이상 없을 때 "값이 없음"을 알게 됩니다.

---

Java 코드로 구현

아래는 이진 검색을 구현한 간단한 Java 코드입니다:

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        // 1. 정렬된 배열 준비
        int[] array = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
        int target = 14; // 찾고자 하는 값

        // 2. 이진 검색 실행
        int result = binarySearch(array, target);

        // 3. 결과 출력
        if (result == -1) {
            System.out.println("값 " + target + "을(를) 배열에서 찾을 수 없습니다.");
        } else {
            System.out.println("값 " + target + "은(는) 배열의 인덱스 " + result + "에 있습니다.");
        }
    }

    // 이진 검색 함수
    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; // 중간 인덱스 계산 (오버플로 방지)

            // 중간 값이 target인 경우
            if (array[mid] == target) {
                return mid;
            }

            // 중간 값이 target보다 클 경우, 왼쪽 검색
            if (array[mid] > target) {
                right = mid - 1;
            }
            // 중간 값이 target보다 작을 경우, 오른쪽 검색
            else {
                left = mid + 1;
            }
        }

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

---

코드 설명

1. 배열 초기화: 정렬된 배열과 검색할 값을 준비합니다.
2. binarySearch 함수: 검색 범위를 좁히며 값을 찾습니다.
   • left와 right는 검색 범위의 시작과 끝을 나타냅니다.
   • mid는 검색 범위의 중간을 계산합니다.
3. 조건에 따른 범위 조정:
   • 중간 값이 target보다 크면 right를 mid - 1로 조정합니다.
   • 중간 값이 target보다 작으면 left를 mid + 1로 조정합니다.
4. 값을 찾지 못하면 -1 반환: 배열에 target이 없을 때를 처리합니다.

---

실행 예시

배열 {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}에서 target = 14를 찾는다고 가정합니다:

1. 첫 번째 반복: left=0, right=9, mid=4
   • array[mid] = 10
   • 10 < 14이므로 오른쪽 탐색 → left = 5
2. 두 번째 반복: left=5, right=9, mid=7
   • array[mid] = 16
   • 16 > 14이므로 왼쪽 탐색 → right = 6
3. 세 번째 반복: left=5, right=6, mid=5
   • array[mid] = 12
   • 12 < 14이므로 오른쪽 탐색 → left = 6
4. 네 번째 반복: left=6, right=6, mid=6
   • array[mid] = 14 → 값 찾음!

---

포인트

• 시간 복잡도: O(log⁡n), 배열이 클수록 효율적입니다.
• 주의: 배열이 정렬되지 않으면 이진 검색이 동작하지 않습니다!

궁금한 점이나 추가 설명이 필요하면 말씀해주세요! 😊