[자료구조] 검색의 활용

[연습 문제 1] 선형 검색의 스캐닝 과정을 상세하게 표시하는 프로그램을 작성하시오.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main() {
    int num,key,cnt=0;
    printf("[선형 검색]\n");
    printf("검색 개수: ");scanf("%d",&num);
    
    int *arr = (int*)malloc(sizeof(int)*(num+1));//보초를 위한 공간 추가 할당
    for(int i=0;i<num;i++){printf("X[%d]: ",i);scanf("%d",&arr[i]);}
    arr[num] = key;

    printf("검색값: ");scanf("%d",&key);

    printf("검색을 시작합니다....\n\n");
    printf("    |");for(int i=0;i<num;i++)printf("%3d",arr[i]);printf("\n");
    printf("----+");for(int i=0;i<num*3+1;i++)printf("-");
    printf("\n");
    for(int i=1;i<=num+1;i++){
        if(i == num+1){
            printf("\n검사실패...\n");
            break;
        }
        
        printf("    |");for(int j=0;j<i*2+cnt;j++)printf(" "); printf("*\n");
        printf("  %d |",i);for(int i=0;i<num;i++)printf("%3d",arr[i]);printf("\n");
        if(arr[i-1]==key){
            printf("\n검사완료!\n");
            printf("%d는 x[%d]에 존재합니다.",key,i);
            break;
        }
        
        cnt ++;
    }
}

[연습 문제 2] 검색할 값과 같은 값을 갖는 요소가 하나이상일 경우 같은 값 중 가장 앞으로 요소를 찾는 함수를 작성하라.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int bin_search2(int arr[],int n,int key){
    int LOW,MID,HIGH;

    LOW = 0;
    HIGH = n -1;
    do{
        MID = (LOW + HIGH)/2;
        if(arr[MID] == key) return MID;
        else if(arr[MID] < key) LOW = MID + 1;
        else HIGH = (MID -1);
        /**
        중앙값보다 검색하고자 하는 값이 큰 경우
        -> (중앙값+1)를 LOW로
        
        중앙값보다 검색하고자 하는 값이 작은 경우
        -> (중앙값-1)를 HIGH
         */
    }while(LOW <= HIGH);
    return -1;
    /**
    LOW  : 검색 범위 맨 앞의 인덱스 == pl
    MID  : 검색 범위 가운데 인덱스  == pr
    HIGH : 검색 범위 맨 뒤의 인덱스 == pc
    */

}

int main(){
    int num,key,cnt=0;
    printf("이진검색\n");
    printf("요소 개수: ");scanf("%d",&num);

    int *arr = (int*)malloc(sizeof(int)*num);
    printf("오름차순으로 입력하세요.\n");

    while(num > cnt){
        if(cnt == 0){
            printf("x[%d]: ",cnt);
            scanf("%d",&arr[cnt]);    
            cnt ++;
        }
        else{
            printf("x[%d]: ",cnt);
            scanf("%d",&arr[cnt]);    
            if(arr[cnt-1] <= arr[cnt]) cnt ++;
            else printf("오름차순으로 다시 입력하세요.\n");
        }
    }
    printf("검색값: ");scanf("%d",&key);

    int idx  = bin_search2(arr,num,key);
    if(idx == -1) puts("검색에 실패했습니다.");
    else{
        for(int i=idx;i>=1;i--){
            if(arr[i-1]!=key){
                printf("첫번째 검색값 %d는 arr[%d]에 있습니다.",key,idx);
                break;
            }
        }
        // printf("%d는 arr[%d]에 있습니다.",key,idx);
    }
    free(arr);
}