꿈 꾸는 누렁이

미루고 미뤄왔던 보간 탐색에 대한 포스팅이다!!!

위에는 보간 탐색의 기반이 될 탐색의 원리를 설명해 놓은 글이다. 무려, 4개월 ~ 5개월 전에 내가 작성했던 글이다. 지금 봐도 상당히 디테일하게 잘 작성한 것 같은데 , 코드라던가 실행 결과 등을 제대로 올리지는 않았더라.

그래서 이번 포스팅에서 보간 탐색과 함께 이진 탐색의 재귀적 구현, 이진 탐색의 반복문 구현까지 원쁘라스투(1+2) 형태로 포스팅 들어간다.

먼저, 보간 탐색이 Main 이니 보간 탐색에 대해 살펴보도록 한다.

보간 탐색이란?

이진 탐색을 살짝 더 효율적으로 개선한 것이다! 기존의 이진 탐색의 경우 다음과 같이 탐색이 진행되는데,

3번의 이진 탐색이 진행되었고, 그 3번의 이진 탐색 안에는 수 많은 계산들과... 수 많은 조건 검사 등으로 인해 그냥 선형 순차 탐색만도 못한 효율이 나와버렸다. 그 이진 탐색 시켜주려고 정렬까지 한 것을 생각해보면 억울하다. 

물론.. 미미한 성능 차이이고, 데이터가 더 많고, 타겟이 더 안쪽에 있었을 때에는 분명히 이진탐색이 개쩔긴하다ㅋㅋ 예를 들기 위해서 극단적으로 말해본 것이다.

왜 위와 같이 선형 순차 탐색보다도 못한 결과가 일어났을까? 왜냐하면...

첫 번째, 데이터가 생각보다 앞에 있었기 때문이다.
두 번째, 죽으나 사나 수행하는 반 절 나누기로 인해서 절반 지점부터 시작하는 탐색 시작 위치가 문제이다.

그래서 데이터가 극 초반이나, 극 후반에 존재할 경우에도 계속 반절부터 시작할꺼냐! 라는 생각에서부터 시작되었다.

첫 번째 원인은 타겟이 치우져 있는 것은 우리가 어떻게 할 수 없는 것이다. 사용자가 찾겠다고 하는 타겟이 거기 있는걸 무슨 수로 해결하는가?

그렇다면 두 번째, 앞으로 절반 지점부터 시작하지 않으면 되지않을까? 

그래서 이렇게 바꿔봤다. 이 공식은 아마도 수학 센세들이 힘들게 연구한 공식이 아닐까 한다. 저 공식은 

"내가 찾는 값과 그 값이 저장되어 있는 위치는 비례하기 때문에 전체 길이에서
대충 이 정도 어디쯤에느으으은~~ 있지 않겠는가?"

를 이야기하는 공식이다. 그럴 수 밖에 없는게 이진 탐색과 마찬가지로 정렬되어 있는 데이터 세트를 대상으로 하기 때문에 당연히 전체 길이에서 찾으려는 값은 어림잡아 이쯤에 있겠거니 하고 추측해볼 수 있는 것이지 않겠는가?

그래서 그걸 실제로 구현해 본 예이다.

그런데 다음과 같은 예에서 탈출 조건에 문제가 있다. 

위의 조건대로 데이터 세트와 타겟을 2로 조정하여 실행해보면 실행이 무한 루프에 빠진다. 즉, 탈출 해야하는데 탈출 조건을 충족시키지 못해서 무한 루프에 빠지는 것이다.

그렇다면 왜 이전 탈출 조건인 start <= end 조건은 먹히지 않는걸까? 그 이유를 아래에 정리해 보았다.

그도 그럴 것이, 새로 정의된 공식으로 인해서 정해지는 index 값은 "너가 찾는 타겟 값은 전체 길이 중에 대충 어디어디 쯤에 있어~" 라고 이야기해주는 것과 같다. 그렇다보니, 아무리 start 와 end 가 갱신된다고 하더라도 이전과 비슷한 index 값을 계산해서 내놓을 확률이 높다. 더군다나 start가 1밖에 증가하지 않은(범위가 겨우 인덱스 하나 줄어든) 상황에서는 더더욱 그럴 확률이 높다. 이런 와중에 갱신된 범위가 target이 포함되지 않는 상황까지 되어버린 것이다. 그러면 아주 그냥 삼위일체이다.

위의 예시 상황으로 보자면 다음과 같은 입장들이 되는 것이다.

새 공식 曰 : target 2는 인덱스 0 쯤에 있어~, index = 0 ~
start, end 曰 : 오 마침 index가 0이고 index+1이 start로 넘어오니 결국, 범위가 하나 밖에 안 줄었네?
arr[start], arr[end] 曰 : 3 ~ 9 값이군.
target 曰 : 난 2인데!!!! 왜 3 ~ 9를 보고 있냐!!! 다음 재귀 호출 때 탈출해라!!!
                   [ 재귀 호출 ]
탈출 조건 曰 : 응~ start <= end 조건 성립해서 탈출 안 해 ~
새 공식 曰 : (범위가 하나 줄은 것 가지고는 결과는 그대로겠네..?) 음.. 뭐.. target 2는 인덱스 0쯤에 있어~, index = 0 ~
                   [... 무한 반복 ...]
컴파일러 曰 : '신발장 크레파스 놈들이!!!!!!!!!!!!!!!!!!!!! 꽥(무한 루프 터.짐.)'

위의 대화가 탈출 조건과 새 공식의 순서가 코드와 조금 다르긴 하지만 문제는 없다. 결국은 같기 때문이다.

뭐 위 대화까지 보고도 이해가 안된다면 내 잘못이다. 설명을 못한 것이다. 근데 이게 글로만 설명하기 겁나 애매하고 짜증난다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아래는 코드와 실행결과이다. 탈출 조건까지 최종 수정된 보간 탐색과 이진 탐색의 재귀적 구현과 반복적 구현까지 모두 넣어 놓은 3종 세트인 것이다.

코드와 실행 결과

없는 값으로 인해 탐색 실패 결과

탐색 성공

이진 탐색을 구현해보았다.

이진 탐색에 대해 간단하게 기록하기 전에 이진 탐색의 전제 조건에 대해서 기록을 먼저 해보겠다.

이진 탐색의 전제 조건

• 이진 탐색은 오름차순이든 내림차순이든 관계없이 '정렬'이 되어있는 연속된 배열 자료구조에서 적용된다.

이러한 전제를 갖는 자료구조를 대상으로 탐색을 진행하는 것이 이진 탐색이다. 그렇다면 왜 이진 탐색은 저런 전제를 갖나?
그 해답은 이진 탐색의 정의에 있다.

이진 탐색이란?

타겟을 탐색할 때, 전체 자료구조의 (1)최대한 가운데 위치하는 값과 타겟을 (2)비교하여 탐색의 범위를 비교한 가운데 값을 기준으로 왼쪽과 오른쪽 중 하나로 탐색의 (3)범위를 좁히고 다시 좁혀진 범위에서 최대한 가운데 값을 다시 비교하고 탐색의 범위 결정을 반복하여 타겟을 탐색하는 알고리즘이다.

이진 탐색은 반복이 들어간다. (4)반복이 들어간다는 의미는 탈출 조건이 필요하다는 뜻이다.

이 탈출 조건은 매우 당연하고 자연스럽다.

허나, 이 이유를 알기 전에 범위를 잡는다는 개념을 알아야 한다. 범위를 잡는 것은 여러 케이스들이 있을테지만 선형(배열) 자료 구조에서의 범위를 잡는다는 행위에 대해서 적어보겠다.

탐색할 범위를 잡는다는 것은 시작 인덱스와 끝 인덱스를 잡는 것이다. 쉽게 말해서 시작과 끝을 잡아야한다. 배열에서 시작과 끝을 잡는다는 의미는 시작 인덱스 값과 끝 인덱스 값을 잡는다는 것이다.

자, 그러면 세 가지의 경우가 있다.

• 시작 인덱스 < 끝 인덱스
  : 정말 당연한 것이다. 탐색할 범위의 양 시작과 끝을 잡고 있다고 보면 된다.
• 시작 인덱스 == 끝 인덱스
  : 이런 경우가 나올 수 있을까? 나올 수 있다. 시작 인덱스이자 끝 인덱스에 위치한 값이 타겟인 경우다. 운이 안 좋은 가장 최악의 경우인 것이다. 어떻게 이렇게 제일 끝에 나올 수 있어? 재수 없단 말이지! 이런 뉘앙스의 최악의 경우를 뜻하고, 이런 경우까지 고려하여 알고리즘의 성능 평가를 시행한다 실제로.
• 시작 인덱스 > 끝 인덱스
  : 이런 경우가 가능할까? 알고리즘이고 말고를 떠나서 글자 자체만 보더라도 불가능하다. 고로, 탈출 조건이 된다. 이 경우는 해당 배열 자료구조에 타겟에 해당하는 값이 없기 때문에 발생하는 경우이다. 시작 인덱스와 끝 인덱스가 같은 바로 위의 경우에도 타겟이 검출되지 않으면 발생하는 경우이고, 이 경우에는 조건 제어를 통해 반복을 탈출해야한다. 왜냐고? 배열에 타겟이 없으니까!

자 그렇다면 구현하는데에 생각하는 순서를 좀 정리해본 것이 위 본문에서의 괄호 안의 숫자들이다.

• (1)최대한 가운데 위치하는 값(을 구한다)
• (2)비교
• (3)범위를 좁힌다(결정한다)
• (4) 탈출 조건

위 순서에 해당하는 부분들을 주석으로 표시해봤다.