오늘은 이분 탐색에 대해서 글을 써보려고 합니다.
이분 탐색이란게 뭐냐면 이분은 일단 두개로 분할한다는 의미이고 탐색은 말 그대로 내가 원하는 자료를 찾기 위해 탐색 한다는 의미입니다.
간단한 예시를 통해 이분 탐색의 동작 과정을 살펴 봅시다
아래 그림과 같은 배열의 크기가 9이고 데이터는 다음과 같이 나열되어 있다고 합시다
여기서 우리가 찾아야 할 수는 23(index : 5)입니다.
탐색 방법은 여러가지가 있습니다
가장 쉬운 방법으로는 index 0에서 8까지 순차적으로 탐색하는 방법이 있을 것입니다.
순차 탐색의 경우 하나씩 다 방문할 것이고 결국 5번째에 23이라는 숫자를 찾게 될 것입니다
시간 복잡도 측면에서 바라보면 O(n)의 시간이 나오겠죠
하지만 이분 탐색의 경우 2번만에 찾을 수 있습니다.
왜 2번만에 찾을 수 있는지 이분 탐색 과정을 살펴 봅시다
살펴 보기 앞서 이분 탐색을 하기위해서는 다음과 같은 준비 과정이 필요합니다
* 배열은 정렬 된 상태여야 한다.
left : 탐색할 배열의 시작을 의미
right : 탐색할 배열의 마지막을 의미
mid : left와 right의 중간 값을 의미
동작은 다음과 같이 진행합니다
0. 종료 조건은 left가 right보다 값이 커지면 종료입니다.
1. data[mid]값이 내가 찾는 값인가?
- 맞다면 검색 종료
2. 현재 data[mid]값이 내가 찾는 값이 아니고 찾는 값보다 작은 수라면?
- left = mid + 1;
3. 현재 data[mid]값이 내가 찾는 값이 아니고 찾는 값보다 큰 수라면?
- right = mid - 1;
아주 간단합니다.
그러나 글로만 이해가 잘 안되실 수 있으니 그림으로 살펴 보겠습니다
초기값은 다음과 같습니다
left = 0
right = 8
mid = (left + right) / 2
자 여기서 이분 탐색을 고안한 사람은 심플하게 mid값을 위주로 판단하도록 설계 했습니다.
현재 data[mid]는 18이 되겠네요
2번 동작을 진행해야 합니다.
2번 동작을 진행하면서 의문점을 가질 수 있습니다.
left는 23이네 우리가 찾던 수가 맞네. 검색 종료 하자 이렇게 생각 하실 수 있습니다. 그렇게 구현할 수도 있을 것 같네요
하지만 시간복잡도 측면에서 다 같은 O(log n)이므로 의미가 없습니다.
계속 진행 해보도록 하겠습니다.
left, right mid가 한곳에 뭉쳐졌네요. mid값에 23이 있으니 우리는 종료 합시다.
이렇게 2번에 찾을 수 있습니다 하지만 없는 경우라면??
23이 아니라 27을 찾는다고 해봅시다
27을 찾는다면 일단 위의 과정과 똑같이 동작합니다.
그러나 내가 찾고자 하는 값이 없고, 현재 mid값 보다 큰 값이기 때문에 2번 동작에 의해 다음과 같이 됩니다
이 경우 0번 종료 조건에 의하여 탐색이 종료 됩니다.
이 경우 우리는 해당 수를 찾지 못했다는 return 값을 전송해야겠죠.
이 과정을 코드로 한번 옮겨봅시다
- 재귀로도 구현 할 수 있으나 재귀 코드는 여러분들에게 맡기도록 하겠습니다.
- 종료조건 및 처리과정을 재귀형식으로 조금만 생각해도 짤 수 있으니, 재귀 공부 후에 한번 짜보세요
int list[10000];
bool BinarySearch(int x)
{
int left = 0;
int right = n-1;
//0번 종료 조건
while(left <= right)
{
int mid = (left+right)/2;
//1번 조건
if(list[mid] == x) return true;
//2번 조건
else if(list[mid] < x)
{
left = mid + 1;
}
//3번 조건
else
{
right = mid - 1;
}
}
//해당 값 미 발견시
return false;
}