[알고리즘] Binary Search - Proof & Time Complexity

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

- 입력 배열 arr에는 같은 값이 존재하지 않으며, 값 기준 오름차순 정렬되어서 저장되어 있다고 가정하자.

- x는 우리가 찾으려고 하는 값이다.

 

Binary Search by While Loop

---

int binarySearch(const int arr[], int size, int x) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = (left + right) / 2;  // left <= mid <= right
        if (arr[mid] == x) {
            return mid;
        }

        if (x < arr[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

 

Proof by Invariant

Invariant:

arr[i] = x인 i가 존재한다면, left ≤ i ≤ right가 항상 성립한다.

 

Invariant는 최초에 성립하고, Invariant가 깨질 수 있는 코드가 전혀 없다.

 

따라서

1. arr[i] = x인 i가 존재한다면, while loop 내에서 반드시 return이 된다.

2. arr[i] = x인 i가 존재하지 않는다면, right < left인 순간이 반드시 찾아와서 while loop이 끝나게 되고, -1을 return 한다.

 

 

Recursive Binary Search

---

int binarySearch(const int arr[], int size, int x) {
    // base
    if (size == 0) {
        return -1;
    }

    // step
    int mid = size / 2;
    if (arr[mid] == x) {
        return mid;
    }
    if (x < arr[mid]) {
        return binarySearch(arr, mid, x);
    }
    int result = binarySearch(arr + mid + 1, size - mid - 1, x);

    if (result == -1) {
        return -1;
    }
    return result + mid + 1;
}

 

Proof by Induction

주장:

binarySearch() 함수는

- arr[i] = x인 i가 존재한다면, i를 return 한다.

- arr[i] = x인 i가 존재하지 않는다면, -1을 return 한다.

 

 

Base:

size = 0인 경우

'어떤 i에 대해서 arr[i] = x'가 성립할 방법이 없다. → Vacuously True

 

 

Step:

아래 3가지 경우를 나누어서 보아야 한다.

- Case 1: arr[mid] = x인 경우

- Case 2: arr[mid] > x인 경우

- Case 3: arr[mid] < x인 경우

 

1. arr[mid] = x인 경우

'return m;'을 하기 때문에 주장이 성립한다.

 

2. arr[mid] > x인 경우

arr[m] > x이라는 것은, x 값이 arr[0], arr[1], ... , arr[mid-1] 중에 존재한다는 것과 같다.

→ binarySearch(arr, mid, x)가 정확하다고 가정한다면, 이는 i를 반드시 return 한다.

→ binarySearch(arr, size, x)도 i를 반드시 return 한다.

 

3. arr[mid] < x인 경우

arr[m] < x이라는 것은, x 값이 arr[mid+1], arr[mid+2], ... , arr[size-1] 중에 존재한다는 것과 같다.

→ binarySearch(arr+mid+1, size-mid-1, x)가 정확하다고 가정한다면, 이는 i를 반드시 return 한다.

→ binarySearch(arr, size, x)도 i를 반드시 return 한다.

 

Time Complexity

T(n) = 1 + T(n/2) = 1 + 1 + T(n/4) = ... = logn

∴ O(logN)