#13 이진 탐색(이진 검색, Binary Search) with 재귀함수

- A와 B가 내기를 했다.
- 1 ~ 100까지의 숫자 중 하나를 B가 골랐을 때 A가 4번의 시도 안에 그 숫자를 맞추면 A가 이기고 그렇지 못하면 B가 이긴다.
- B는 A가 틀린 숫자를 얘기하면 해당 숫자가 자신이 고른 숫자보다 up인지 down인지 말해줘야한다.

Q. 이때 A가 숫자를 맞추는 가장 효율적인 방법은 무엇일까?
A. 숫자 범위의 중간(혹은 중간즈음)을 선택하는 것이다.

ex) B는 94를 골랐다.
1번 시도 : A는 1 ~ 100의 중간인 50을 얘기한다. / 오답이므로 B는 UP이라고 얘기한다.
2번 시도 : A는 51 ~ 100의 중간즈음인 75를 얘기한다. / 오답이므로 B는 UP이라고 얘기한다.
3번 시도 : A는 75 ~ 100의 중간즈음인 87을 얘기한다. / 오답이므로 B는 UP이라고 얘기한다. 
4번 시도 : A는 87 ~ 100의 중간즈음인 94를 얘기한다. / 정답이므로 B는 A한테 500억을 줘야한다.

- 위의 얘기가 이번 글의 주제인 이진 탐색(Binary Search)과 연관이 있다.

- 아래의 글을 먼저 읽어보자

2023.01.22 - [자료구조 및 알고리즘] - #2 시간복잡도(좋은 알고리즘?) / 최악의 경우는 Big-O

#2 시간복잡도(좋은 알고리즘?) / 최악의 경우는 Big-O

---

● 이진 탐색(이진 검색, Binary Search)

const arr = [3, 7, 9, 1, 2];

- 위와 같이 정렬되지 않은 배열이 있을 때 그 안에서 특정 값을 찾는다고 해보자

- 당연히 그 값이 어느 index(위치)에 있는지 알 수 없기 때문에 (index = 0)부터 하나씩 차례대로 검사를 해야한다.

- best는 arr[0]에 찾고자 하는 값이 있는 것이다.
- worst는 arr[arr.length - 1]까지 검사를 해도 찾고자 하는 값이 없는 것이다.
ㄴ이 경우 모든 원소를 검사하는 것이므로 O(N)의 시간복잡도를 갖는다.

---

- 만약 배열이 정렬돼 있는 상태라면 어떻게 될까?

const arr = [1, 2, 3, 7, 9];

- arr 배열의 중간값을 찾는다. 이 경우 arr[2] = 3 이다.
- 찾고자 하는 값이 중간값(arr[2] = 3)인지 먼저 확인한다. best는 (찾는값 = 중간값)인 경우이다.
- (찾는값 != 중간값)인 경우 (찾는값 > 중간값) 혹은 (찾는값 < 중간값)인지 확인한다.
- (찾는값 > 중간값)인 경우 중간값 기준으로 오른쪽 데이터만 보면된다.(arr[3] ~ arr[4])
- (찾는값 < 중간값)인 경우 중간값 기준으로 왼쪽 데이터만 보면된다.(arr[0] ~ arr[1])

- 위와 같은 방식의 검사를 이진 탐색(이진 검색, Binary Search)이라고 한다.

- 즉, 이진 탐색은 한 번씩 검사를 수행할 때마다 검색을 해야하는 영역이 절반으로 줄어드는 것이다.

- 이때의 시간복잡도를 O(logN)이라고 한다. 즉, 이진 검색은 배열이 정렬돼 있는 상태일 때 O(logN)의 시간복잡도를 갖는다.(배열이 정렬돼 있을 때 가장 효율적인 검색 방법)

- 중요한건 반드시 배열이 정렬돼 있어야 한다는 것이다.

---

● 재귀함수(재귀호출)

- 이진 검색을 재귀함수(재귀호출)를 이용해 구현해보자

int main() {
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int index;
    index = binarySearch(arr, 0, 9, 14); // (배열, 배열의첫번째인덱스, 배열의마지막인덱스, 찾고자하는값)
    
    if(index == -1) {
    	printf("찾는 값 없음\n");
    } else {
    	printf("arr[%d]에 찾는 값 있음 \n", index);
    }
    return 0;
}

- 이진 검색에서 가장 먼저 해야할 일은 배열의 중간값을 찾는 것이다.

int binarySearch(int* arr, int left, int right, int target) { // (배열, 배열의첫번째인덱스, 배열의마지막인덱스, 찾고자하는값)
    if(left > right) {
        return -1; // 배열 안에 찾고자하는 값이 없는 경우
        // (중간값 < 찾는값) or (중간값 > 찾는값) 모두 찾고자하는 값이 없는 경우 결국에는 (left > right) 상태가 된다.
    }

    int middle = (left + right) / 2; // 배열의 중간 인덱스
    
    if(arr[middle] == target) { // best : (중간값 == 찾는값)
    	return middle;
    }
    
    if(arr[middle] < target) {
    	// (중간값 < 찾는값) -> 중간값 기준 오른쪽의 데이터만 본다.
        // (배열, 배열의첫번째인덱스, 배열의마지막인덱스, 찾고자하는값)
    	return binarySearch(arr, (middle + 1), right, target);
    } else {
    	// (중간값 > 찾는값) -> 중간값 기준 왼쪽의 데이터만 본다.
        // (배열, 배열의첫번째인덱스, 배열의마지막인덱스, 찾고자하는값)
    	return binarySearch(arr, left, (middle - 1), target);
    }
}

 

cf) 아래의 영상을 보고 정리했다.

https://www.youtube.com/watch?v=NSonAgxIfuc&t=151s