C언어 - 탐색

선형 탐색

• 배열의 원소를 순서대로 하나씩 꺼내서 탐색키와 비교

#include <stdio.h>

#define SIZE 5

int main() {
    int key;
    int list[SIZE] = {1, 2, 3, 4, 5};

    printf("탐색할 값을 입력하시오: ");
    scanf("%d", &key);

    for (int i = 0; i < SIZE; i++) {
        if (list[i] == key)
            printf("탐색 성공, 인덱스 : %d", i);
    }
    
    return 0;
}

이진 탐색

• 선형 탐색에 비해 속도가 매우 빠르나 배열이 정렬이 되어 있어야 함
• 배열의 중앙에 있는 값을 탐색키와 비교
• 주로 고정된 데이터에 대한 탐색에 적합
  

#include <stdio.h>

#define SIZE 10

int binarySearch(int list[], int size, int key);

int main() {
    int list[SIZE] = {1, 2, 3, 5, 6, 7, 11, 20, 30, 50};
    int key;

    printf("탐색할 값을 입력하시오: ");
    scanf("%d", &key);
    printf("탐색 성공, 인덱스: %d\n", binarySearch(list, SIZE, key));
}

int binarySearch(int list[], int size, int key) {
    int low, high, middle;
    low = 0;
    high = size - 1; // 첫번째 탐색 -> 배열의 양 끝 맞추기

    while (low <= high) {
        printf("탐색 범위: %d ~ %d\n", low, high);
        middle = (low + high) / 2; // 중간 위치 지정

        if(key == list[middle]) // 일치하면 탐색 성공
            return middle;
        else if(key > list[middle])
            low = middle + 1; // 중간 요소 값 초과하는 값으로 하한 재설정
        else
            high = middle - 1; // 중간 요소 값 미만 값으로 상한 재설정
    }
}

탐색할 값을 입력하시오: 30
탐색 범위: 0 ~ 9
탐색 범위: 5 ~ 9
탐색 범위: 8 ~ 9
탐색 성공, 인덱스: 8