탐색 - 순차 탐색과 이진 탐색

탐색 - 순차 탐색과 이진 탐색

순차탐색(sequential search)

• 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색
• 정렬 유무에 상관 없이 가장 앞에 있는 원소부터 확인
• O(N)의 시간 복잡도

int main(void)
{
    int n;
    char *word;

    word = malloc(sizeof(char) * 100);
    scanf("%d %s", &n, word);
    array = (char **)malloc(sizeof(char *) * n);
    for (int i = 0; i < n; i++)
    {
        array[i] = malloc(sizeof(char) * LENGTH);
        scanf("%s", array[i]);
    }
    for (int i = 0; i < n; i++)
    {
        if (!strcmp(array[i], word))
        {
            printf("%d번째 원소입니다\n", i + 1);
            founded = 1;
        }
        if (!founded)
            printf("원소를 찾을 수 없습니다.\n");
    }
}

이진 탐색(binary search)

• 이미 정렬이 돼 있는 데이터에서 사용 가능
• 탐색 범위를 절반씩 좁혀가며 탐색
• 탐색 범위 중앙에 있는 원소와 반복적으로 비교
• O(logN)의 시간복잡도

int search(int start, int end, int target)
{
    if (start > end)
        return -9999;
    int mid = (start + end) / 2;
    if (a[mid] == target)
        return mid;
    else if (a[mid] > target)
        return (search(start, mid - 1, target));
    else
        return (search(mid + 1, end, target));
}