이분 검색(Binary Search)-재귀(Recursion)

이분 검색(Binary Search)-재귀(Recursion)

---

 

2024.10.16 - [Computer Science & Engnieering/Algorithm] - 이분 검색 알고리즘(Binary Search)

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

재귀 함수의 재귀 호출은 분할정복의 하향식 문제풀이 방식과 원리가 같습니다.  그래서 반복(Iteration)을 이용한 이분검색 알고리즘을 재귀 호출 방식으로 만들고자 합니다.

 

이분 검색 설계하기

1. [분할] 배열을 가운데 원소(y)를 기준 반으로 분할합니다. 찾으려는 값(x)이 y와 같으면 알고리즘을 종료하고 x가 작으면 왼쪽 배열을 크면 오른쪽 배열을 선택합니다.
2. [정복] 선택한 배열에 x가 있는지 재귀적을 이분검색합니다.
3. [취합] 선택한 배열에서 찾은 답이 최종 답입니다.

 

이분 검색 재귀의 예시

찾으려는 값은 5이고 배열이 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13이라고 가정하면

1. [분할] 배열을 분할하는데 가운데 7과 찾는 값 5를 비교하여 5 < 7이니 왼쪽 배열을 검색합니다. 1, 2, 3, 4, 5, 6
2. [정복] 왼쪽 배열에 5가 있는지 결정합니다. 있으므로 x는 왼쪽 배열에 존재합니다.
3. [취합] 왼쪽 배열에 5가 있으니 전체 배열에 5가 존재합니다.

정복에서 해답을 구해온다고 가정하였는데 해답을 어떻게 구하는지는 작성할 필요가 없습니다. 즉 해답을 어떻게 구하는지에 대한 세부사항은 염려할 필요가 없습니다.

이분 검색 재귀 구현 코드

class Recursion {
    public int bsr(int[] S, int x, int low, int high) {
        // 재귀의 종료 조건
        if(low > high) {
            return 0;
        }

        int mid = (low + high) / 2; // 중간 인덱스 계산

        if(S[mid] == x) {
            return mid;
        }
        else if (S[mid] > x) {
            return bsr(S, x, low, mid - 1);
        }
        else {
            return bsr(S, x, mid + 1, high);
        }
    }
}

public class BinarySearchRecursion {
    public static void main(String[] args) {
        Recursion recursion = new Recursion();
        int[] S = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};    // 배열 S
        int x = 5;  // 찾으려는 값 x
        
        int location = recursion.bsr(S, x, 0, (S.length - 1));
        System.out.println("x의 위치 : " + location);
    }
}

 

 

구현에 대한 그림

1. 배열에서 중간값을 구합니다. 중간값은 7이므로 7과 5를 비교하고 7보다 작으므로 왼쪽 배열을 선택합니다.
2. 왼쪽 배열에서 중간값을 구합니다. 중간값은 3이므로 3과 5를 비교하고 중간값보다 커서 오른쪽 배열을 선택합니다.
3. 오른쪽 배열에서 중간값을 구합니다. 중간값은 5이고 찾으려는 값은 5로 같으므로 배열의 인덱스를 반환합니다.