[탐색] 이진 탐색 알고리즘 정리 (Binary Search)

 

📌 이진 탐색 알고리즘 (Binary Search)

- 정렬된 배열에서 특정 값을 효율적으로 찾는 방법

- 중간값을 반복적으로 확인하며 탐색 범위를 반으로 줄여나가는 방식으로 작동

- 정렬된 배열에서만 동작한다.

 

 

💡 이진탐색 알고리즘 구현

 

#1. 재귀 방식

- 간결하지만, 너무 많은 재귀 호출 시 스택 오버플로우 위험

import java.util.Arrays;

public class BinarySearch {
    //이진 탐색 함수 (재귀 방식)
    public static int binarySearchRecursive(int[] array, int target, int left, int right){
        if(left > right){ //탐색 범위가 없으면 값이 존재하지 않음
            return -1;
        }

        int mid = (left + right) / 2; //중간값 계산
        if(array[mid] == target){
            return mid;
        } else if (array[mid] > target) { //타겟값이 중간보다 작으면 왼쪽으로
            return binarySearchRecursive(array, target, left, mid - 1);
        }else{ //타겟이 중간값보다 크면 오른쪽으로
            return binarySearchRecursive(array, target, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] array = {2, 4, 7, 10, 23, 34, 45, 56, 78};
        int target = 23;

        //배열 정렬
        Arrays.sort(array);
        
        int resultRecursive = binarySearchRecursive(array, target, 0, array.length - 1);
        System.out.println("재귀 방식 결과 " + (resultRecursive != -1 ? "인덱스 " + resultRecursive : "값이 없음"));
      
    }
}

 

 

 

#2. 반복 방식

- 메모리 효율성이 좋음

import java.util.Arrays;

public class BinarySearch {
    //이진탐색 함수(반복 방식)
    public static int binarySearchIterative(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while(left <= right){
            int mid = (left + right) / 2 //중간값 계산
            if(array[mid] == target){
                return mid;
            } else if (array[mid] > target) { //타겟이 중간보다 작으면 왼쪽으로
                right = mid - 1;
            }else{
                left = mid + 1; //타겟이 중간보다 크면 오른쪽으로
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {2, 4, 7, 10, 23, 34, 45, 56, 78};
        int target = 23;

        //배열 정렬
        Arrays.sort(array);
        
        int resultIterative = binarySearchIterative(array, target);
        System.out.println("반복 방식 결과 " + (resultIterative != -1 ? "인덱스 " + resultIterative : "값이 없음"));
    }
}