[알고리즘] 이분 탐색(Binary Search)
이분 탐색이란 ?
단어 그대로 해석하면 두 부분으로 쪼개면서 탐색한다는 것이다. 이진탐색이라고도 한다.
여기서 중한 포인트는 기본적으로 '탐색'이라는 것이다.
분할정복은 어떤 전체 문제를 해결하기 위해 부분적으로 나눠들어가면서 분할하여 부분 문제를 해결하는 방식이라면,
이분탐색은 위 메커니즘과 유사하게 두 부분으로 나누어 들어가긴 하지만, 특정 값 또는 자료를 찾는 '탐색'이다.
가장 쉽게 이해하는 예시로는 Up & Down 게임이 있다.
1 ~ 100 까지 수 중 상대방이 17로 정했다고 가정할 때, 우리는 수를 맞추기 위해 절반인 50부터 시작한다.
그리고 상대가 다운이라 하면, 그 다음 절반인 25를 물을 것이다. 그 다음으론 12 ...
50 - 25 - 12 - 18 .. 반으로 쪼개가면서 수를 찾는 방식이다.
이런식으로 구간 내 절반을 잘라가면서 값을 찾아나가는게 기본적인 이분 탐색 원리이다.
백준 1920 문제에서의 포인트는 '수가 존재하는지'만 알아내면 되기에 중복 원소에 대한 고려는 하지 않고 구현한다.
임의의 배열이 주어지고 우리가 찾고자 하는 값을 key라고 하며 이분 탐색이 어떻게 이루어지는지 과정이다.
우리가 찾는 값(key)이 7이라면 위와 같이 진행된다.
주황색 칸은 탐색 범위이고, 이분 탐색을 하기 위해서는 배열이 반드시 정렬되어있어야 한다. *주의
기본적인 메커니즘은 다음과 같다.
1. 탐색 범위내에 배열의 중간 인덱스를 구한다.
2. 중간 인덱스의 값과 key값을 비교한다.
3. 값이 중간 값보다 작다면 왼쪽 부분을, 값이 중간보다 크다면 오른쪽 부분을 탐색하고, 같다면 해당 인덱스를 반환하고 종료한다.
찾으려는 값이 없는 경우도 존재한다. 위 이미지와 같은 과정을 거치며 언젠가는 탐색 범위가 한 개인 경우가 있다는 것을 볼 수 있다. 근데 한개의 인덱스에 있는 값이 찾으려는 값과 동일하지 않다면, 그대로 끝나게 된다.
쉽게 말해 탐색 범위의 왼쪽 끝과 오른쪽 끝이 같은 경우(범위가 한개일때)까지 탐색을 했는데 그 값이 key값과 같지 않을 경우 해당 배열에는 key 값이 존재하지 않는다는 의미이다.
보통 해당 값을 못찾을 경우 Java의 Arrrays.binarySearch 방식을 이용해 음수를 반환한다.
이때 시간 복잡도는 이진 트리 형태의 경우 대다수가 O(logN) 의 시간 복잡도를 갖는다.