[자바 알고리즘] 이진탐색

알고리즘 코딩테스트를 기반으로 내용을 정리하고 추가했습니다.

이진탐색

이진 탐색(binary search)

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘.
데이터가 정렬되어 있지 않은 상태에서 결과가 정확하지 않거나 동작하지 않기에 정렬되어있다는 있다는 것을 기억해야한다. 정렬이 안되어있다면, 선형 탐색이 적합하다.

  - 중앙값 비교를 통한 대상 축소 방식
  - 시간 복잡도 O(logN)

이진탐색의 핵심원리

오름차순일경우 (내림차순은 반대로)
    1) 현재 데이터셋의 중앙값을을 선택
    2) 중앙값 > 타킷 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택
    3) 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
    4) 과정 1~3을 반복하다가 중앙값 == 타킷 데이터일 때 탐색을 종료

이진탐색의 그림

이진탐색의 구현방법

재귀적 구현

    • 재귀 호출을 통해 탐색 범위를 줄여가며 구현.
	• 간결하고 이해하기 쉬운 방식이지만, 깊은 재귀 호출로 인해 스택 오버플로우 위험이 있음(특히 데이터 크기가 클 때). 

//예시 코드
public class BinarySearchRecursive {
    public static int binarySearchRecursive(int[] arr, int target, int low, int high) {
        // 종료 조건: 탐색 범위가 유효하지 않을 때
        if (low > high) {
            return -1; // 타겟이 없으면 -1 반환
        }
        // 중앙값 계산
        int mid = low + (high - low) / 2;
        // 타겟과 중앙값 비교
        if (arr[mid] == target) {
            return mid; // 타겟 값 발견
        } else if (arr[mid] > target) {
            // 타겟이 중앙값보다 작으면 왼쪽 탐색
            return binarySearchRecursive(arr, target, low, mid - 1);
        } else {
            // 타겟이 중앙값보다 크면 오른쪽 탐색
            return binarySearchRecursive(arr, target, mid + 1, high);
        }
    }
    public static void main(String[] args) {
        int[] arr = {3, 7, 13, 15, 23, 35, 38, 41, 46, 49, 55, 67, 68, 72, 77, 86};
        int target = 55;
        int result = binarySearchRecursive(arr, target, 0, arr.length - 1);
        System.out.println("result);
    }
}

반복문 구현

	• 재귀 호출 대신 while 루프를 사용하여 탐색.
	• 재귀적 구현보다 스택 오버플로우 위험이 없으며, 메모리 효율이 더 좋음.

public class BinarySearchIterative {
    public static int binarySearchIterative(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            // 중앙값 계산
            int mid = low + (high - low) / 2;
            // 타겟과 중앙값 비교
            if (arr[mid] == target) {
                return mid; // 타겟 값 발견
            } else if (arr[mid] > target) {
                // 타겟이 중앙값보다 작으면 왼쪽 탐색
                high = mid - 1;
            } else {
                // 타겟이 중앙값보다 크면 오른쪽 탐색
                low = mid + 1;
            }
        }
        return -1; // 타겟 값이 없는 경우
    }
    public static void main(String[] args) {
        int[] arr = {3, 7, 13, 15, 23, 35, 38, 41, 46, 49, 55, 67, 68, 72, 77, 86};
        int target = 55;
        int result = binarySearchIterative(arr, target);
        System.out.println(result);
    }
}

참고자료(출처)
책 - 알고리즘 코딩테스트
유튜브 - 이진탐색