* first가 last보다 큰 경우 탐색은 종료가 된다. 그리고 이 경우는 탐색에 실패했다는 것을 의미한다.
코드구현
#include <iostream>
// 이진 탐색 알고리즘
int BSearch(int ar[], int len, int target){
int first=0; // 인덱스 시작 변수
int last = len-1; // 인덱스 마지막 변수
int mid; // 분할 지점 변수
while(first<=last)
{
mid = (first+last)/2; // 분할 지점 계산 후 저장
if(target == ar[mid]){ // 탐색할 인덱스가 찾는 값이라면
return mid; // 탐색을 종료하고 해당 값(mid)을 반환한다. 탐색완료
}
else{ // 그것이 아니라면 탐색 대상(인덱스 범위)을 반으로 줄인다.
if(target <ar[mid]){ // 찾을 값이 탐색했던 값보다 작은 값이라면
last = mid - 1; // 탐색했던 위치에서 -1을 해주고 last 변수에 저장한다.
}
else{ // 찾을 값이 탐색했던 값보다 큰 값이라면
first = mid + 1; // 탐색했던 위치에서 + 1을 해주고 first 변수에 저장한다.
} // 시작 위치 재정의
}
}
return -1; // while문을 돌려도 탐색에 실패했으면 -1이라는 값을 반환
}
int main() {
int arr[] = {1, 3, 5, 7, 9}; // 배열안에 데이터는 정렬되어 있어야 한다.
int idx;
idx = BSearch(arr, sizeof(arr)/sizeof(int), 7);
if(idx == -1){
printf("탐색 실패\n");
}
else{
printf("값 저장 인덱스 : %d\n",idx);
}
idx = BSearch(arr, sizeof(arr)/sizeof(int), 4);
if(idx == -1){
printf("탐색 실패\n");
}
else{
printf("값 저장 인덱스 : %d\n",idx);
}
return 0;
}
//// result
값 저장 인덱스 : 3
탐색 실패
- 여기서 봐야할 부분이 있다.
// 1 옳은 경우
if(target <ar[mid]){
last = mid - 1;
}
else{
first = mid + 1;
}
// 2 잘못된 경우
if(target <ar[mid]){
last = mid;
}
else{
first = mid;
}
- 위 코드에서 2번째와 같이 증감과 감소하지 않고 last와 first 변수에 저장하면 처음 mid에 저장했던 인덱스 값의 배열요소도 다시 새로운 탐색의 범위에 포함된다. 하지만 이는 불필요한 작업이다.
* 이미 탐색에 있어서 mid의 배열 요소를 탐색했기 때문이다.
- 탐색 대상 하나 더 추가한다고 크게 문제가 되나요 ?
- 사실 위의 질문에는 문제삼지 않을 수 있지만 다른 문제가 발생할 수 있다.
- 경험해 보기 위해 -1과 +1을 빼고 실행해보면 무한루프에 빠져 프로그램이 종료되지 않는 문제를 볼 수 있다.
무한루프 ... 무한 반복... 프로그램이 종료되지 않아 .....
- 탐색 대상이 배열에 존재하지 않을 경우 first에 저장된 값이 last보다 커져서 반복문을 탈출할 수 있어야 하는데, 위와 같은 코드를 작성하면 first에 저장된 값은 last보다 커질 수가 없다.
- 기본적으로 세 변수에 저장된 인덱스 값은 항상 다음의 식을 만족하도록 알고리즘이 구현되어 있다.
first <= mid <= last
* 이렇게 mid 변수 안에 저장된 값을 가감 없이 first, last의 값을 저장하는 것만으로는 first값이 last값보다 커질 수가 없다.
시간복잡도 계산하기 : 최악의 경우(worst case) 기준
- 순차 탐색 알고리즘에 비하면 상대적으로 복잡한 편 - 수학적 사고를 요하는 정도 - 이진 탐색 알고리즘을 보면서 연산횟수를 대표하는 연산 찾기
while(first <= last)
{
mid = (first+last)/2 // 탐색 대상의 중앙 찾기
if(target==ar[mid]){ // 중앙에 저장된 값이 타겟이라면
return mid;
}
else { ... } // 타겟이 아니라면
}
- 이진 탐색역시 순차 탐색과 마찬가지로 ‘==’ 연산을 연산횟수로 대표하는 것으로 볼 수 있다.
Q. 데이터의 수가 n개일 때, 최악의 경우에 발생하는 비교연산의 횟수는 얼마나 되는가?
- 이 질문에 순차 탐색과 같이 O(n)을 말했다면 틀렸다 또한, ‘몇 번이요’라고 해도 틀릴 확률이 높다.
* 이진 탐색 알고리즘의 시간 복잡도 계산 - 데이터의 수가 n개일 때 비교연산은 총 몇 회가 진행되는지 알아보자 1. 처음 데이터 수가 n개일 때의 탐색과정에서 1회의 비교연산 진행 2. 데이터의 수를 반으로 줄여서 그 수가 n/2개일 때의 탐색과정에서 1회 비교연산 진행 3. 데이터의 수를 반으로 줄여서 그 수가 n/4개일 때의 탐색과정에서 1회 비교연산 진행 4. 데이터의 수를 반으로 줄여서 그 수가 n/8개일 때의 탐색과정에서 1회 비교연산 진행 “ n이 얼마인지 결정되지 않았으니 이 사이에 도대체 몇 번의 비교연산이 진행되는지 알 수가 없다 ! ” 5. 데이터의 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회의 비교연산 진행 - 여기서 알 수 있듯이 최악의 경우, 탐색 대상의 데이터 수가 n개로부터 시작해서 반씩 줄어 마지막에는 1개가 되는데, 반씩 줄어드는 과정을 몇 번 거치는지 알 수 없다는 것이 문제이다.
Q. 데이터의 수가 n일 때, 최악의 경우에 발생하는 비교연산의 횟수는 어떻게 되는가?
- 수학을 조금 응용해보자.
- 데이터의 수가 8인 경우, 8이 1이 되기까지 2로 나누는 과정을 총 3회 거쳐야 한다. 1. 8이 1이 되기까지 2로 나눈 횟수 3회, 따라서 비교연산 3회 진행 2. 데이터가 1개 남았을 때, 이 때 마지막으로 비교연산 1회 진행
- 이는 데이터의 수 n을 대상으로 다음과 같이 일반화할 수 있다. 1. n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행 2. 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회 진행
- 이렇게 비교연산의 횟수를 구했으니, 최악의 경우에 대한 시간 복잡도 함수 T(n)은 다음과 같이 정리된다.
T(n) = k + 1
- 이젠 k를 구할 차례이다. 그런데 n이 1이 되기까지 2로 나눈 횟수가 k이니 n과 k에 관한 식을 다음과 같이 세울 수 있다.
* 해당 수식을 보면 2로 나누는 것은 1/2를 곱하는 것과 같다는 단순한 사실만 알면 이해할 수 있는 수식이다. 이는 2로 몇 번을 나누어야 1이 되는가에 대한 답을 주는 수식일 뿐이다. 실제로 위의 수식에서 n에 8을 k에 3을 대입하면 식은 성립한다.
- 해당 수식을 k 에 관한 식으로 다시 정리하면 아래와 같이 된다.
- 이제 정리된 최종 수식의 양 변에 밑이 2인 로그를 취하는 것이다. 그럼 식은 아래와 같이 정리가 된다.
- 이렇게 k는이다. 따라서 이진 탐색 알고리즘의 최악의 경우에 대한 시간 복잡도 함수 T(n)은 다음과 같다.
- 그리고 최악의 경우 비교연산 횟수는 k+1이니 로그뒤에 n+1을 해줘야하는 것이 더 옳지않은가라고 생각할 수 있다. 하지만 +1이 중요한 것이 아니라 데이터의 수 n이 증가함에 따라 비교연산의 횟수가 로그적으로 증가한다는 사실이다.
“ 식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다.
- 즉 n에 대한 식 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이므로 +1은 중요하지 않다.
