[CS50] 알고리즘 - 선형 검색, 이진 검색

배열과 검색 방법

배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조이다.

 

컴퓨터는 값들에 접근할 때 배열의 인덱스를 사용해 하나씩 접근한다.

 

만약 어떤 값이 배열 안에 속해 있는지를 찾기 위해서는 배열이 정렬되어 있는지 여부에 따라 검색 방법이 달라진다.

 

 

선형 검색

배열이 정렬되어 있지 않은 경우 선형 검색을 사용한다.

 

선형 검색은 배열의 처음부터 끝까지 하나씩 증가시키며 각 값을 방문하여 그 값이 존재하는지를 검사하는 방법이다.

 

아래는 선형 검색의 의사코드이다.

For i from 0 to n–1
    If i'th element is 50
        Return true
Return false

위 의사코드는 배열의 첫 번째 요소부터 마지막 요소까지 순차적으로 검사해 찾고자 하는 값이 있는지 확인한다.

 

찾고자 하는 값이 발견되면 true를 반환하고 끝까지 검색해도 발견되지 않으면 false를 반환한다.

 

 

이진 검색

배열이 정렬되어 있는 경우 이진 검색을 사용할 수 있다.

 

이진 검색은 배열 중간 인덱스부터 시작해 찾고자 하는 값과 비교하면서 값이 중간 값보다 작은 경우는 왼쪽 절반을, 큰 경우는 오른쪽 절반을 다시 검색하는 방법이다.

 

이 과정을 반복해서 값을 찾는다.

If no items
    Return false

If middle item is 50
    Return true

Else if 50 < middle item
    Search left half

Else if 50 > middle item
    Search right half

이 의사코드는 배열이 비어 있는 경우 false를 반환한다. 중간 값이 찾고자 하는 값과 일치하면 true를 반환한다.

 

찾고자 하는 값이 중간 값보다 작으면 배열의 왼쪽 절반을, 크면 오른쪽 절반을 검색한다.

 

이진 검색은 배열이 정렬되어 있어야만 사용할 수 있고 시간 복잡도는 O(log n)으로 매우 효율적이다.

 

 

선형 검색 예제

#include <stdio.h>
#include <stdbool.h>

bool linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return true;
        }
    }
    return false;
}

int main(void) {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 4;

    if (linear_search(arr, n, target)) {
        printf("Found %d\\n", target);
    } else {
        printf("Did not find %d\\n", target);
    }
}

 

 

이진 검색 예제

#include <stdio.h>
#include <stdbool.h>

bool binary_search(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int middle = left + (right - left) / 2;

        if (arr[middle] == target) {
            return true;
        }

        if (arr[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return false;
}

int main(void) {
    int arr[] = {2, 3, 4, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 4;

    if (binary_search(arr, n, target)) {
        printf("Found %d\n", target);
    } else {
        printf("Did not find %d\n", target);
    }
}

 

 

References

모두를 위한 컴퓨터 과학 (CS50 2019)

모두를 위한 컴퓨터 과학 (CS50 2019)