Binary Search (이진탐색)

이진탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾기 위해 사용하는 효율적인 알고리즘입니다. 시간 복잡도가 O(logn)이기 때문에 데이터가 많아질수록 유리합니다. 이진탐색은 배열의 중간 요소와 목표 값을 비교하고, 범위를 절반씩 줄여가며 검색을 반복합니다.

이진탐색 동작 과정

1. 중간값 선택: 배열의 중간에 위치한 값을 선택합니다.
2. 비교: 선택된 중간값과 찾고자 하는 값을 비교합니다.
   • 만약 값이 같으면 찾기 성공.
   • 값이 작으면 중간값 기준 왼쪽 절반만 확인.
   • 값이 크면 중간값 기준 오른쪽 절반만 확인.
3. 반복: 범위를 좁혀가며 중간값을 반복적으로 선택하고 비교합니다.

 

public class BinarySearchExample {

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

        int left = 0;
        int right = numbers.length - 1;
        int result = -1; // 값이 없을 경우를 대비한 초기값

        while (left <= right) {
            int mid = (right - left) / 2; // 중간 인덱스 계산

            if (numbers[mid] == target) {
                result = mid; // 값이 일치하면 인덱스 저장
                break;
            } 
            if (numbers[mid] < target) {
                left = mid + 1; // 중간값보다 크면 오른쪽 절반 탐색
            } else {
                right = mid - 1; // 중간값보다 작으면 왼쪽 절반 탐색
            }
        }

        if (result != -1) {
            System.out.println("Target " + target + " found at index " + result);
        } else {
            System.out.println("Target " + target + " not found in the array.");
        }
    }
}