0708 스키마에듀 수업

0708.pdf

11.45MB

// 선형 검색
#include <stdio.h>
#include <stdlib.h>

//요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색
int search(const int a[], int n, int key){
    int i = 0;

    while(1){
        if(i == n){ //배열을 끝까지 봤는데도 검색하려는 값이 없음.
            return -1; //검색 실패
        }

        if( a[i] == key){
            return i; //검색 성공
        }

        i++;
    }
}


int main(void) {

    int nx, ky;
    puts("선형 검색");
    printf("요소 개수: ");
    scanf("%d", &nx);

    int *x = calloc(nx, sizeof(int)); //요소개수가 nx인 int형 배열 x를 생성

    for(int i=0; i< nx; i++){
        printf("x[%d]", i);
        scanf("%d", &x[i]); //배열 요소 입력
    }
    
    printf("검색값: ");
    scanf("%d", &ky);  //검색값 입력

    int idx = search(x, nx, ky);

    if(idx == -1){
        puts("검색에 실패했습니다.");
    }else{
        printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
    }

    free(x); //배열 x를 해제

    return 0;
}

 

보초법

// 선형검색
#include <stdio.h>
#include <stdlib.h>

//*- 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형검색(보초법)--

int search(int a[], int n, int key){

    int i=0;
    a[n] = key; //배열의 끝에 보초를 추가
    while(1) {
        if( a[i] == key){
            break;
        }
        i++;
    }

    return i == n ? -1: i;
    //i가 보초를 가리키고 있을 경우 탐색 실패한것. -1 반환
}

int main(void){
    
    int nx, ky; //요소개수, 탐색값

    puts("선형 검색 (보초법) ");
    printf("요소 개수: "); scanf("%d", &nx);
    int *x = calloc(nx+1, sizeof(int)); //길이가 (nx+1)인 int형 배열 x 생성

    for(int i=0; i<nx;i++){
        printf("x[%d]: ",i);
        scanf("%d", &x[i]);
    }

    printf("검색값: ");
    scanf("%d", &ky);
    int idx = search(x, nx, ky);

    if(idx == -1){
        puts("검색 실패");
    }else{
        printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
    }
    free(x);

    return 0;
}

 

// 이진탐색
#include <stdio.h>
#include <stdlib.h>

//*- 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 이진탐색 

int bin_search(const int a[], int n, int key){

    int pl = 0;     //검색 범위 맨 앞의 인덱스
    int pr = n-1;    //검색 범위 맨 끝의 인덱스

    do{
        int pc = (pl + pr) / 2; //pc: 검색범위 한가운데 인덱스
        if(a[pc] == key){    //검색 성공
            return pc;
        }else if(a[pc] < key){
            pl = pc+1;        //검색 범위를 뒤쪽 절반으로 좁힘
        }else{ //a[pc] > key
            pr = pc-1;
        }
        
    }while(pl <= pr);

    return -1;        //while문을 빠져나오면 검색 실패
}

int main(void){
    
    int nx, ky; //요소개수, 탐색값

    puts("이진 검색");
    printf("요소 개수: "); scanf("%d", &nx);
    int *x = calloc(nx, sizeof(int)); //길이가 (nx+1)인 int형 배열 x 생성

    printf("오름차순으로 입력하세요.\n");

    printf("x[0]: ");
    scanf("%d", &x[0]);

    for(int i=1; i<nx; i++){
        
        do{
             printf("x[%d]: ",i);
            scanf("%d", &x[i]);
            
        }while(x[i] < x[i-1]);        //배열 앞의 값보다 작으면 다시 입력
       
    }

    printf("검색값: ");
    scanf("%d", &ky);
    int idx = bin_search(x, nx, ky);

    if(idx == -1){
        puts("검색 실패");
    }else{
        printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
    }
    free(x);

    return 0;
}