Binary Search Algorithm

* 배열의 인덱스가 1부터 시작한다고 가정합니다.

([1] = 1번째 와 같이 이해하기 쉽도록)

 

- 알고리즘 정의

정렬이 된 배열에서 찾고자 하는 원소가 나올 때 까지 탐색하는 알고리즘.

탐색하는 방법은 low, high의 가운데, mid와 비교하여

찾고자 하는 값이 mid보다 크면 오른쪽, 작으면 왼쪽의 배열에서 다시 탐색한다.

 

- Pseudocode

// Iterative way
public static index BinSearch (int n, keyType[] S, keyType x) {
    index location, low, high, mid;
    low = 1;
    high = n;
    location = 0;
    
    while (low <= high && location == 0) {
        mid = floor((low + high) / 2);
        if (x == S[mid]) location = mid;
        else if (x < S[mid]) high = mid - 1;
        else low = mid + 1;
    }
    
    return location;
}

크기가 n인 배열 S에서 x를 찾는 알고리즘.

location에 x의 위치가 저장되는데, 0은 찾지 못한 경우이다.

low <= high, 즉 탐색을 끝까지 안 한 경우,

location == 0, 즉 x를 찾지 못한 경우 계속 while문을 반복한다.

mid 값을 low, high의 평균으로 설정하고, S[mid]의 값와 x를 비교한다.

같으면 해당 위치(mid)를 location에 저장,

x가 작으면 예상되는 위치는 S[mid] 보다 왼쪽에 있는 경우이기에 high값을 조정,

x가 크면 오른쪽에 있는 경우이기에 low값을 조정한다.

 

// Recursive way
// S: global
public static index location (index low, index, high) {
    index mid;
    if (low > high) return 0;
    
    mid = floor((low + high) / 2);
    if (x == S[mid]) return mid;
    if (x < S[mid]) return location(low, mid - 1);
    return location(mid + 1, high); 
}

위 방식과 동일하다.

단, Divide and Conqure 방식을 사용하는 것 뿐이다.

 

- Time complexity

Basic Operation: S[mid] 와 x의 비교

Input Size: n (Size of S) (n = 2^k라 가정)

 

* Worst case:

[Θ(lg n)]