이진탐색 (BinarySearch)

분할 정복 알고리즘의 일부 탐색법이다.

 

검색해야 할 대상(arr)을 절반씩 잘라서, 찾으려는 숫자(target)의 범위를 포함하는 서브 대상에서 다시 똑같은 방법으로 찾는다.

단, 절반으로 잘라서 찾는 분할정복법의 특정 상 속도는 굉장히 빠르지만, 배열은 정렬이 되어 있어야 한다는 제약이 따른다.

 

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]  이라는 배열이 있고, 여기서 8을 찾는다고 가정해보자.

left는 찾으려는 현재 배열의 가장 작은 값(가장 왼쪽 값)

right는 찾으려는 현재 배열의 가장 큰 값(가장 오른쪽 값)

mid는 찾으려는 현재 배열의 중간값 (가장 가운데 값)

을 뜻한다.

 

 - 1차 계산

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

현재 배열에서 left는 1, right는 11이 된다.

mid를 구할 때는 주의할 점이 있다. right에서 2를 나누면 안된다.

그 이유는 2차 계산부터 나올 것이지만, right를 2로 나누는 것은 1차 계산에서 첫 배열의 연산 시에만 유효한 것이다.

mid는 '(right + left) / 2'와 같이 구해야 한다. 따라서 (11+1)/2 = 12/2 = 6이 된다.

 

mid를 기준으로 왼쪽의 서브 배열과 오른쪽의 서브배열을 나눌 수 있다.

왼쪽 서브 배열은 1~5가 되며 (left ~ mid-1)

오른쪽 서브 배열은 7~11이 된다. (mid+1 ~ right)

서브 배열에서 mid인 6은 포함되지 않는다.

 

서브 배열을 결정할 때, 계산 과정 중 mid값보다 큰경우, 작은경우, 같은경우 3가지를 검사하게 된다.

이 케이스는 target 8이 mid 6보다 큰 경우이므로 mid+1을 다음 계산할 서브리스트의 left로 세팅하는 것이다.

만약 target과 mid가 같은 경우가 나왔다면 여기서 종료됐을 것이다. 

 

마지막 계산에서 보겠지만, 서브 배열이 1개인 경우는 해당 배열을 리턴한다.

서브 배열을 검사할 때는 배열의 갯수가 2개 이상인 경우에만 진행하도록 한다.

단, 정렬이 되어있지만 모든 값이 채워져 있다고는 보장할 수 없으므로, 마지막에 값이 같은지 검사해보고, 값이 틀리다면 찾는 값은 존재하지 않는 것이다.

 

1차 계산에서 구해진 오른쪽 서브 리스트는 다음과 같다.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

 

 - 2차 계산

[7, 8, 9, 10, 11]

1차 계산에서 구한 서브 배열에서 left는 7, right는 11이 된다.

 

left는 1차 계산 마지막에서 mid값인 6을 바탕으로 갱신한 값이다.

left에 mid값인 6을 그대로 쓰지 않고 mid+1 = 7을 left에 저장한 이유는 1차 계산에서 mid값이 target과 같은 값일 경우 mid값을 그대로 리턴하면 되기 때문이다.

결국 mid과 target이 다르기 때문에 mid에 1을 더해서 찾을 범위를 줄이는 것이다.

 

mid는 '(right+left)/2' 이므로, (11+7)/2 = 18/2 = 9이다.

 

 * 만약 1차 계산처럼 right/2를 했다면 11/2 = 5가 나오므로 전혀 이상한 값이 나온다.

   mid값은 'left와 right의 중간값'이다. 따라서 전체 배열에서 /2를 하는게 아니라, 현재 배열(서브배열) 내에서 중간값을 구해야 한다.

 

target은 8이며 mid인 9보다 작으므로 왼쪽 서브배열을 다시 찾아야 한다.

이번엔 왼쪽 서브 배열이 필요하므로, left는 그대로 두고 right를 수정한다.

right는 mid-1값으로 수정한다.

mid값을 쓰지 않고 mid-1값을 쓰는 이유는 위에서, 2차 계산에서 left에 mid+1을 하는 이유와 같은 맥락이다.

 

따라서 left는 7, right는 8이다.

mid는 '(right+left)/2' 이므로, (8+7)/2 = 15/2 = 7이다.

 

2차 계산에서 구해진 왼쪽 서브 리스트는 다음과 같다.

[7, 8, 9, 10, 11]

 

 

- 3차 계산

[7, 8]

2차 계산에서 구한 왼쪽 서브 배열에서 left는 7, right는 8이 된다.

mid = (right+left)/2 = (8+7)/2 = 15/2 = 7이 된다.

target이 8이고, mid가 7이므로, target은 mid보다 크다.

따라서 오른쪽 서브 배열을 봐야 한다.

 

그런데 1차 계산에서 설명했듯이, 서브배열의 검사는 해당 서브배열의 길이가 2 이상일 때만 진행한다.

현재 오른쪽 서브 배열은 [8]로 원소가 하나뿐이다.

따라서 찾으려는 target의 값과 mid+1의 값이 동일한지 검사해야 한다.

target = 8,

mid+1 = 7 + 1 = 8

이 동일하므로, 오른쪽 서브 배열의 첫 번째 요소인 8을 리턴하면 원하는 숫자를 찾게 된다.

만약 8이 빠져있을 수 있으므로, 마지막에 정말 원하는 숫자인지 검사하여 값이 있는지 없는지를 체크하도록 하자.

 

3차 계산에서 구해진 오른쪽 서브리스트는 다음과 같다.

[8]

 

 

위 과정을 그림으로 표현하면 다음과 같다.

 

정리

1. 이진 탐색 트리는 기존의 배열을 절반으로 나누어 찾으려는 범위를 줄여나가는 분할정복법 종류의 하나다.

 - 절반으로 줄이기 때문에 배열은 반드시 정렬되어 있어야 한다.

 - 절반으로 줄여나가기 때문에 시간복잡도는 O(logN)이다.

 

2. left, right, mid의 값 구하기

left = 서브 배열의 가장 작은 값(가장 왼쪽 값), 직전 계산에 나온mid값 보다 1이 큰 것이 서브 배열의 left (mid+1)

right = 서브 배열의 가장 큰 값(가장 큰 값), 직전 계산에 나온mid값 보다 1이 적은 것이 서브 배열의 right (mid-1)

mid = '(right+left)/2', 서브 배열의 중간값

 

3. 서브배열의 검사는 해당 서브 배열의 원소의 개수가 2개 이상일 때만 진행한다.

 - 서브배열의 길이가 1이면 그냥 target과 비교해서 맞으면 리턴, 다르면 값이 없는 것으로 처리한다.

 

4. 정렬이 되어있다고 해서 모든 값이 들어있는 것이 아니다. 원하는 값이 없을 수도 있다. 따라서 마지막에 리턴할 값(mid 또는 mid+1 또는 mid-1)을 반드시 검증한 후 리턴하도록 하자.

 

5. 실제로는 위 배열 원소인 1~11은 주로 인덱스에 활용된다.

위의 예제에서는 인덱스와 숫자자 1:1로 매칭됐다.

예를 들어

첫 번째 요소 1은 인덱스 1(프로그래밍에서는 0)

두 번째 요소 2는 인덱스 2(프로그래밍에서는 1)

...

마지막 요소 11은 인덱스 11(프로그래밍에서는 10)

와 같다.

 

위에서 말했듯이 이진 탐색 트리는 모든 숫자가 '정렬'되어 있을 뿐이지, 원하는 값이 들어있지 않을 수도 있다.

따라서 [1, 100, 101, 102, 104] 에서 102를 찾는다고 가정했을 때,

위에서 말한 것처럼 mid값을 '(right의 값+left의 값)/2'로 찾아버리면 (104+1)/2 = 105/2 = 52가 나온다.

이렇게 하면 mid값보다 큰 100, 101, 102, 104가 서브 트리가 되어버린다.

 

정상적인 경우라면 [1, 100], [101], [102, 104]와 같은 형태로 나뉘어야 하는데,

[1], [100, 101, 102, 104]과 같이 나누어진 것이다.

이는 성능 측면에서 매우 비효율적이며, 이진탐색을 제대로 활용하는 것이 아니다.

 

따라서 해당 원소의 값으로 계산하는 것이 아니라, 해당 원소의 인덱스로 계산해야 한다.

(right의 인덱스 + left의 인덱스)/2

 

총 5개이므로 left를 0, right를 4로 놓는다면 mid는 (4+0)/2 = 4/2 = 2가 된다.

따라서 mid값은 2가 되며, 해당 인덱스 원소의 값은 101이다.

102는 101보다 큰 값이므로 left값을 mid+1 = 2+1 = 3번 인덱스로 수정해서 동일하게 진행하면 된다.