순차탐색과 이진탐색

순차탐색 - 탐색해야할 자료들을 처음부터 마지막까지 순차적으로 비교하는 탐색 방식.
순차탐색의 장점 - 자료들이 정렬되어있지 않아도 탐색이 가능하다.
순차탐색의 단점 - 리스트가 길어지면 비효율적이다.

순차탐색 구현

#include <stdio.h>
int i, key, count, n, result;
int arr[5] = {9, 5, 8, 3, 7};

int search() 
{
    for (i = 0; i < n; i++) 
    {
        count++;
        if (arr[i] == key)
        {
            return count;
        }
    }
    return -1;
}

int main() 
{
    n = sizeof(arr) / sizeof(int);
    printf("탐색할 값은? ");
    scanf("%d", &key);
    result = search();
    if (result == -1) 
        printf("탐색 실패입니다.");
    else 
        printf("탐색 성공이며 탐색 횟수는 %d회입니다.", result);
    
    return 0;
}

이진탐색 - 자료들을 반씩 나누어서 탐색하는 방식.
이진탐색의 장점 - 탐색범위를 절반씩 줄여가기 때문에 시간복잡도가 O(logN)이다.
이진탐색의 단점 - 자료들이 반드시 정렬되어 있어야 탐색이 가능하다.

이진탐색 구현

#include <stdio.h>
int i, key, count, n, result;
int arr[6] = {1, 3, 5, 7, 9, 11};

int search(int start, int end)
{
    int middle;
    if (start <= end)
    {
        count++;
        middle = (start + end) / 2;
        if (key == arr[middle]) return count;
        else if (key < arr[middle]) return search(start, middle - 1);
        else if (key > arr[middle]) return search(middle + 1, end);
    }
    return -1;
}

int main()
{
    n = sizeof(arr) / sizeof(int);
    printf("탐색할 값은? ");
    scanf("%d", &key);
    result = search(0, n - 1);
    if (result == -1) 
        printf("탐색 실패입니다.");
    else 
        printf("탐색 성공이며 탐색 횟수는 %d회입니다.", result);
    
    return 0;
}