2. Search algorithm

void Seqsearch(int n, const keytype S[], keytype x, index& location){
    location = 1;
    while(location <= n && S[location] != x)
        location ++;
    if(location > n)
        location = 0;
}
 

void binarySearch(int n, const keytype S[], keytype x, index& location)
{
    index low, high;
    low = 1; high = n;
    location = 0;
 
    while(low <= high && location == 0){
        mid = (low + high) / 2;
        if(x == S[mid])location = mid;
        else if(x < S[mid]) high = mid - 1;
        else low = mid + 1;
    }
}
 

Sequential Search와 다르게 Binary Search는 사용 조건이 있다. 배열이 무조건 정렬이 되어 있어야 한다. 정렬이 안되어 있으면 binary search을 할 수 없다.

Binary Search에서 B.C는 어떤 상황인지 바로 한눈에 보인다.

배열 [1,2,4,6,19,25,30]에서 6을 Binary Search로 찾으면 한번 만에 찾을 수 있다. ( ∵ T(n) = 1 )

W.C를 찾는 것은 한 눈에 안 보인다. Binary Search는 반을 쪼개가면서 검색을 하는 알고리즘이다. 따라서, Binary Search에서 W.C는 찾으려는 숫자가 맨 처음에 있거나 맨 마지막에 있을때이다. 또 다른 하나가 있는데 그것은 바로, 우리가 찾을려는 숫자가 배열 안에 없을 때이다.

W.C 경우 T(n)을 구하는 것은 좀 어렵다. Binary는 반을 쪼개가면서(다른 말로는 처음과 마지막을 반으로 나누면서) 검색을 한다. 숫자 일일이 계산해서 표로 작성을 하면 아래와 같다.

Input size	Count
1	1
2	2
3	2
4	3
5	3
7	3
8	4
9	4
16	5

2, 4, 8, 16일 때 값이 하나씩 커진다. 이를 보고 T(n)을 유추하면 아래와 같다.

저기 있는 lg n은 밑이 2인 log n인데 보통 생략하고 저렇게 쓴다고 한다. 그 이유는 아직 모르겠지만 더 공부하다 보면 왜 저렇게 생략하는지 알게 될거 같다.

또한 log n 양 옆에 붙은 기호는 소수점 내림이라고 생각하면 된다. 예를 들어 3.141592라는 숫자를 저 기호를 이용하여 표현하면 그 값은 3이 된다.