C Data Structure - 이진 탐색

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

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

이진 탐색의 전제 조건

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

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

이진 탐색이란?

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

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

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

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

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

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

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

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

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

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