이진 탐색(Binary Search) 알고리즘과 시간 복잡도

이진 탐색(Binary Search) 알고리즘과 시간 복잡도

 

이진 탐색(Binary Search)

 

순차탐색이 있으면 이진 탐색도 있다.

이진탐색이란 우선 이진탐색을 하기위해서는 

반드시 정렬이 되어있어야한다.

이진탐색은 정렬된 데이터가 아니면 적용을 할 수 없기 때문이다.

 

우선 이진 탐색은 정렬된 데이터의 집합을 이분화 하면서 탐색하는것이다.

이진 탐색의 원리는 다음과 같다.

 

 

[2] [4] [5] [7] [10] [20] [23] [29] [32]

arr[0]  arr[1] arr[2]  arr[3]  arr[4]   arr[5]     arr[6]    arr[7]    arr[8]

 

이렇게 정렬된배열이 있다고 가정한다.

배열의 이름을 arr이라 가정하고 이 배열을 대상으로 

원하는값이 5라면 5를 찾기위한 이진트리의 원리는 이렇하다.

 

우선 이진탐색을 하기위한 첫번째 시도는

 

첫번째 시도

 

1. 배열의 인덱스의 시작과 끝은 0과 8이다.

2. 0과 8을 합하여 그 결과를 2로 나눈다. (홀수일 경우 소수점은 제외한다.)

3. 2로 나눠서 얻은 결과의 숫자 4를 배열의 인덱스로 취하여 arr[4]에 저장된값을 확인한다.

 

즉, 이진트리는 

배열의 시작과 끝의 중앙에 있는 값을 찾아내 저장되어있는값을 판별하는것이다.

위의 배열에 보이듯이 arr[4]번째값은 10이므로 우리가 찾고자하는 값이 아니다.

 

이렇게 첫번째 시도를 통해 원하는 값이 안나오면 두번째 시도를 시작한다.

 

두번째 시도

 

1. arr[4]에 저장된값 10과 찾고자하는값인 5와 대소를 비교한다.

2. 대소의 비교결과는 arr[4]>5 이므로 탐색의 범위를 인덱스 기준 0~3으로 한다.

3. 다시 한번 배열의 시작인 인덱스 0과 탐색 범위의 끝인 3을 더하여 2로 나누나.

4. 2로 나눠서 얻은 결과의 숫자 1을 배열의 인덱스로 취하여 arr[1]에 저장된 값을 확인한다.

 

이렇데 1번째에선 저장된값이 아니기때문에 배열 arr[4]에 저장된값과 대소 를 비교한다.

이것은 이미 정렬이 되어있기 때문에 가능한 것이다.

대소를 비교했을때 더 작기 때문에 arr[4]부터 인덱스의 끝은 비교대상이 아니므로 제외시킨다.

 

 

[2] [4] [5] [7] [10] [20] [23] [29] [32]

arr[0]  arr[1] arr[2]  arr[3]  arr[4]   arr[5]     arr[6]    arr[7]    arr[8]

 

즉, 배열의 arr[4]부터 끝까지는 필요가 없게되어

배열의 0부터 3까지 첫번째 시도를 시작하면된다.

 

이렇게 첫번째와 두번째 시도를 게속 번갈아가면서 하다보면 값을 찾게될수있다.

이게 바로 이진트리의 원리이다.

이렇듯 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 제거하는 알고리즘이다.

순차탐색과 이진탐색의 성능을 비교해보면 이진탐색이 더 좋다는걸 알 수 있을것이다.

 

반응형

 

이진 탐색(Binary Search) 시간 복잡도

 

순차탐색에 시간 복잡도가 있듯이 이진탐색에도 시간 복잡도가 있다.

순차탐색의 시간 복잡도에서 최악의 경우를 기준으로 두듯이

이진탐색또한 최악의 경우를 기준으로두어 최악의 경우 구할것이다.

 

알고리즘을 예를들어 설명을 하겠다.

 

ex)

 

while(first <= last) 

{ 

mid = (first+last) / 2; 

if(target == ar[mid]) 

{ 

return mid; 

} 

else // 타겟이 아니라면 

{ 

. . .

}

}

 

이러한 알고리즘이라고 대략적으로 설명할 수 있을것이다.

여기서 또한 중심이 되는 특정 연산이 있을것이다.

이 알고리즘속에 있는 == 이것이 연산횟수를 대표하는 연산자라고 볼 수 있다.

이제 데이터의 수가 증가할수록 총 횟수가 몇번증가하는지 알아보자

 

• 처음에 데이터 수가 n개일 때의 탐색과정에서 1회의 비교연산 진행
• 데이터 수를 반으로 줄여서 그 수가 n/2개일 때의 탐색과정에서 1회 비교연산 진행
• 데이터 수를 반으로 줄여서 그 수가 n/4개일 때의 탐색과정에서 1회 비교연산 진행
• 데이터 수를 반으로 줄여서 그 수가 n/8개일 때의 탐색과정에서 1회 비교연산 진행

.

.

.

 

• 데이터 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회 비교연산 진행

 

잠깐 여기서의 문제점을 보면 반으로 줄여서 그수가 1개일때의 탐색과정이 

반으로 줄어드는 과정을 몇번 거치는지 알 수 없다는것이 문제다.

 

무수히 많이 진행 되기때문에 일단 n의 갯수를 8 이라 가정하고 정리를 해보자

데이터의 수가 8이면 

1번 했을때 8

2번 했을때 8/2

3번 했을때 8/4

4번 했을때 8/8

이 되어 총 4번의 비교연산이 진행되었다는걸 알수있다.

이것을 다시 글로 정리해보면

 

• 8이 1이 되기까지 2로 나눈횟수는 3회 즉, 비교연산 3회를 진행
• 데이터가 1개 남있을때, 마지막으로 비교연산을 진행해서 1회 진행

 

으로 볼수 있다. 이제 이 8을 n으로 지정하여 바꿔주면

 

• n이 1이 되기까지 2로 나눈횟수는 k회 즉, 비교연산 k회를 진행
• 데이터가 1개 남있을때, 마지막으로 비교연산을 진행해서 1회 진행

으로 설명할 수 있다. 이를 최악의 경우에 대한 시간복잡도 함수를 T(n)=k+1 으로 할 수 있다.

하지만 이 함수가 아직 완성이 된것은 아니다.

우리는 k를 구해야 하기때문이다.

하지만 앞서 k를 n이 1이되기까지 2로 나눈다고 했으니 이를 식으로 표현할 수 있다.

 

이렇게 식으로 표현 할 수있다. 이제 이 식을 k에 관한 식으로 나타내기위해선 다음과 같이 해야한다.

 

 

k에 관한 식으로 나타내면 이러한 결과가 나타내어진다.

 

이제 이걸 다시 시간복잡도 함수에 대입시켜 완성된 식을 볼 수 있다.

 

 

 

이러한 함수가 만들어진다. 하지만 여기서 +1은 생략이 가능하므로 

가 될 수 있다.

왜 1이 생략이 될 수 있냐면 이 식에서 중요한것은

n이 증가함에 따라서 비교연선의 횟수가 로그적(logarithmic)으로 증가한다는것이다.

즉, n에대한 함수 T(n)을 구성하는 목적은 

데이터의 수의 증가에 따른 연산횟수의 변화 정도를 판단하는것 이므로 +1은 중요하지않다.