TIL 2022-07-27-수

1. 학습한 내용

백준 이진탐색 1920번 풀이

• 풀이

2. 알게 된 내용

이진탐색을 재귀함수로 구현하다가, false로 리턴하는 조건을 잘못 설정해서 틀렸다.
start 인덱스가 end 인덱스보다 크면 그때 false를 리턴하면 된다.
예를 들어서, 12345 배열 중에서 7을 찾으려고 할 때,
처음에는 [0] ~ [4]에 대해 탐색을 진행하는데 [2] 즉 3을 중간값으로 두고 비교했을 때 7이 더 크므로 [2] 이후에 대해서 탐색을 진행한다.
그 다음으로 [3] ~ [4]에 대해 탐색을 진행하고, 이때 중간값인 [3] = 4보다 7이 더 크므로 [3] 이후에 대해서 탐색을 진행한다.
그리고 [4] ~ [4]에 대해 탐색을 진행하고, 이때 중간값인 [4] = 5보다 7이 더 크므로 [4] 이후에 대해 탐색을 진행한다.
그러면 [5] ~ [4]에 대해 탐색을 진행하게 되는데, 이러면 start > end 이기 때문에 올바르지 않은 탐색 구간이라 여기서는 false를 리턴해주면 된다.
이러한 원리로 진행하면 되기 때문에, start > end라면 false를 리턴해주는 방식으로 진행하면 된다!

    static boolean binarySearch(int search_num, int start, int end) {
        if (start > end) {
            return false;
        }
        int pivot = (start + end) / 2;
        if (arr[pivot] == search_num) {
            return true;
        } else if (arr[pivot] < search_num) {
            return binarySearch(search_num, pivot + 1, end);
        } else {
            return binarySearch(search_num, start, pivot - 1);
        }
    }
}