[자료구조 C 언어] C 프로그래밍 기초 - 3 : 순차탐색 (Sequential search), 이진탐색 (Binary search)

이번에는 데이터를 탐색하는 방법에 대해 살펴보겠습니다.

 

1. 순차탐색 (Sequential search)

 

: 말 그대로 원하는 값이 나올 때까지 순서대로 하나하나 비교하며 찾아가는 방식입니다.

EX)
1. 탐색할 값을 입력한다.
2. for (배열 크기만큼 반복)
3. if (탐색할 값이랑 같은지?)
4. 같으면 반복문 종료

EX)

int main (void){

    int key, i;

    int list[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        

    printf("탐색할 값을 입력하시오 : ");

    scanf("%d", &key);

    

    for(i = 0; i < SIZE; i++){

        

        if(list[i] == key)

        {

            printf("찾은 값 = %d\n", list[i]);

            printf("탐색 인덱스 = %d\n", i);

            return 1; // 이걸 넣으면 반복문이 종료되나 봐

        }

        

    }

    printf("주어진 값 %d를 찾지 못했습니다.\n", i);

 

   return 0;

}

 

 

2. 이진탐색 (Binary search)

: 오름 차순으로 정렬된 데이터에 대해서 탐색 범위를 절반씩 줄여가며 찾아가는 방식입니다.

EX)
1. 탐색할 값 입력
2. while(low <= high)
3. middle = (low + high) / 2
4. if(middle 이랑 탐색할 값이 똑같은지?)
-> 반복문 종료
5. else if(middle 보다 탐색할 값이 큰지?)
-> low = middle + 1로 바꾸고 다시 2번으로
6. else (작은지?)
-> high = middle - 1로 바꾸고 다시 2번으로

쉽게 말하면 정렬된 배열 중에 찾고 싶은 값이 배열의 중간 값을 기준으로 앞 뒤 중에 없는 쪽은 버리고 있는 쪽에서만 찾겠다는 것입니다.

앞선 순차탐색처럼 처음부터 끝까지 다 찾는데 쓸데없는 자원 낭비를 하지 않겠다는 목적에서 사용되는 탐색방법입니다.

EX)

int binary_search(int list[], int n, int key){

    

    int low, high, middle;

    low = 0;

    high = n - 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;

        

    }

    

    return -1;

}

 

int main(void){

    int key, index;

    int grade[SIZE] = {2,3,4,12,24,25,123,312,443,610};

    

    printf("탐색할 값을 입력하라 : ");

    scanf("%d",&key);

    

    index = binary_search(grade, SIZE, key);

    

    printf("찾은 인덱스 : %d\n", index);

    printf("찾은 값 : %d\n", grade[index]);

 

   return 0;

}

 

 

 

3. 선택정렬 (Selection sort)

: 데이터를 오름차순으로 정렬해줍니다. 이진탐색 하기 전에 선택정렬을 하는게 좋겠죠?

EX)
1. i = 배열의 첫 번째 값
2. for(배열 크기만큼 반복)
3. min = i
4. 배열의 첫 번째 값보다 큰 값이 나오면 그 값을 min의 배열 값과 바꿈 
6. 2번으로 돌아감

 

EX)

 

int main (void) {

    int list[SIZE] ={12, 23, 2, 4, 13, 123, 6, 56, 21};

    int i, j, temp, min;

    

    for(i = 0; i < SIZE-1; i++){

        

        min = i;

        

        for(j = i+1; j < SIZE; j++){

            if(list[j] < list[min])

                min = j;

        }

        

        if (min != i){

            temp = list[i];

            list[i] = list[min];

            list[min] = temp;

        }

    }

    

    for(i = 0; i < SIZE; i++){

        

        printf("%d\n", list[i]);

        

    }

    

    printf("\n");

 

  return 0;

}