2016. 12. 8. 10:46

안녕하세요. 게임개발자 놀이터입니다.


이번 포스팅에선 이진 탐색 알고리즘에 대해서 적어보려고 합니다.


이진 탐색 알고리즘 (Binary Search)


이진 탐색 알고리즘을 하기 위해선 데이터가 정렬되어있어야 합니다. 


정렬된 데이터가 아니면 적용이 불가능한 알고리즘이기 때문이죠.


코드를 살펴보기 전에 알고리즘에 진행 방식을 보겠습니다.


배열 { 1, 3, 4, 5, 7, 8, 10, 20, 60, 100 } 에서 5를 찾아보겠습니다.


 array[0]

 array[1] 

 array[2]

 array[3]

 array[4]

 array[5]

 array[6]

 array[7]

 array[8]

 array[9]

 1

10 

20 

60 

100 


첫번째 케이스


배열 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눕니다. 그 인덱스에 해당하는 값이 5인지 확인하고 아니라면 5보다 큰지, 작은지 확인합니다.


 (0 (시작 인덱스) + 9 (마지막 인덱스)) / 2 = 4.5 (나머지는 버립니다.) => 4


array[4]는 7 이므로 값이 같지 않으니 대 소 를 비교합니다.


array[4]가 찾고자 하는 값(5)보다 크니 4~마지막 인덱스 까진 탐색에서 제외합니다.



 array[0]

 array[1] 

 array[2]

 array[3]

 array[4]

 array[5]

 array[6]

 array[7]

 array[8]

 array[9]

 1

10 

20 

60 

100 


두번째 케이스


(0 (시작 인덱스) + 3 (마지막 인덱스)) / 2 = 1.5 => 1


array[1] 는 3 이므로 값이 같지 않으니 대 소 를 비교합니다.


array[1]가 찾고자 하는 값(5)보다 작으니 시작인덱스 ~ 1 까지 탐색에서 제외합니다.


 array[0]

 array[1] 

 array[2]

 array[3]

 array[4]

 array[5]

 array[6]

 array[7]

 array[8]

 array[9]

 1

10 

20 

60 

100 



세번째 케이스


(2 (시작 인덱스) + 3 (마지막 인덱스)) /2 = 2.5 => 2


array[2]는 4이므로 값이 같지 않으니 대 소 를 비교합니다.


array[2]가 찾고자 하는 값(5)보다 작으니 시작인덱스~2까지 탐색에서 제외합니다.



 array[0]

 array[1] 

 array[2]

 array[3]

 array[4]

 array[5]

 array[6]

 array[7]

 array[8]

 array[9]

 1

10 

20 

60 

100 


네번째 케이스


(3 (시작 인덱스)  + 3 (마지막 인덱스)) /2 = 3


array[3]은 5이므로 찾고자 하는 값과 같으니 반환하며 탐색을 종료합니다.



위처럼 절반 씩 줄어 들면서 값을 검색하니, 시간 복잡도는 O(Log N)을 가집니다.


값을 못찾았다면, 시작인덱스가 마지막인덱스 보다 커진 경우 탐색을 종료하며 실패를 반환합니다.



예시 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int searchint(int[] intarrays, int index)
{
    int from = 0;
    int to = intarrays.Length - 1;
 
    while (from <= to)
    {
        int mid = (from + to) / 2;
 
        if (intarrays[mid] > index) 
        {
            to = mid - 1;
        }
        else if (intarrays[mid] < index)
        {
            from = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
cs



알고리즘의 종료 조건


위 코드처럼 시작인덱스(from)이 마지막인덱스(to)보다 커지면 종료합니다.

Posted by 시리시안