이분 탐색(Binary Search) 알고리즘

개요

이분 탐색(Binary Search) 알고리즘 간단하게 알아보기

---

이분 탐색이란

이분 탐색은 정렬된 데이터에서 특정 값을 찾는 데 사용되는 알고리즘으로, 시간 복잡도가 O(log n)인 매우 효율적인 탐색 방법입니다.
배열을 두 부분으로 나누며 탐색 범위를 점차 좁혀가는 방식으로 동작합니다.

이분 탐색의 특징

1. 정렬된 데이터에서만 사용할 수 있습니다.
2. 탐색 속도가 빠르며, 특히 데이터의 크기가 커질수록 유리합니다.
3. 순차 탐색(Linear Search)보다 훨씬 적은 연산으로 원하는 데이터를 찾을 수 있습니다.

---

이분 탐색의 원리

1. 배열의 중간값을 기준으로 찾고자 하는 값과 비교
2. 찾는 값이 중간값보다 작으면 왼쪽으로, 크면 오른쪽으로 탐색 범위 조정
3. 탐색 범위를 반복적으로 절반으로 줄여 나가며 찾고자 하는 값을 탐색

---

이분 탐색의 구현

1. 반복문을 이용한 이분 탐색

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; // 값을 찾은 경우
            } else if (array[mid] < target) {
                left = mid + 1; // 오른쪽 범위 탐색
            } else {
                right = mid - 1; // 왼쪽 범위 탐색
            }
        }

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

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

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

 

2. 재귀를 이용한 이분 탐색

public class RecursiveBinarySearch {

    public static int binarySearch(int[] array, int target, int left, int right) {
        if (left > right) {
            return -1; // 값을 찾지 못한 경우
        }

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

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

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

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