[gcc] 바이너리 서치 인접 최소값 , 최대값 이진 탐색

http://suite.tistory.com/

fs 2007 03

그냥 200개~~

 binary search 시간복잡도 O (logn)  ~ 최악 n 근데 별로 쓴일이없다!

그냥~  몇개 안되면 linear search 쓰두뭐~

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

#define MAX_NUM 200

int SELECTION_SORT(int p_ARR_NUM[]){

        int rand_i,loop_i,loop_j;
        int tmp_swap_num=0;
        srand((unsigned int)time(NULL));
        for(rand_i=0;rand_i<MAX_NUM;rand_i++){
                p_ARR_NUM[rand_i]=rand()%1000;
        }
        for(loop_i=0;loop_i<MAX_NUM;loop_i++){
                for(loop_j=loop_i+1;loop_j<=MAX_NUM;loop_j++){

                        // 올림 차순
                        if(p_ARR_NUM[loop_i] > p_ARR_NUM[loop_j]){
                                tmp_swap_num=p_ARR_NUM[loop_i];
                                p_ARR_NUM[loop_i]=p_ARR_NUM[loop_j];
                                p_ARR_NUM[loop_j]=tmp_swap_num;
                        }
                }
//              printf("loop:[%d] = %d\n",loop_i,p_ARR_NUM[loop_i]);
        }

        return 0;
}
int BINARY_SEARCH(int key, int p_ARR_NUM[])
{
        int left=0,mid=0,right=MAX_NUM-1;

        int idx_find=-1;
        int min_idx=0,max_idx=MAX_NUM-1;

        while (right >= left)
        {
                mid = (right + left) / 2;

                printf("middle value:[%d] \n",p_ARR_NUM[mid]);

                if (key == p_ARR_NUM[mid]){
                        //값을 찾음
                        idx_find=mid;
                        break;
                }

                // 키값이 가운데 값보다 클경우 왼쪽값을 올려준다
                if(key >  p_ARR_NUM[mid]){

                        min_idx=mid;
                        max_idx=mid+1;

                        left = mid + 1;
                }
                // 키값이 가운데 값보다 작을 경우 오른쪽값을 내려준다
                if(key <  p_ARR_NUM[mid]){

                        min_idx=mid-1;
                        max_idx=mid;

                        right = mid - 1;
                }

        }
        if(idx_find==-1){

                if(min_idx<0) min_idx=0;
                if(max_idx>MAX_NUM-1) max_idx=MAX_NUM-1;

                printf("입력한 키값 '%d' 에대한 일치 결과를 찾지 못함 ...\n",key);
                printf("인접한 최소값:'%d' , 최대값:'%d'\n\n",p_ARR_NUM[min_idx],p_ARR_NUM[max_idx]);

        }
        return idx_find;
}
int main()
{
        int ARR_NUM[MAX_NUM];
        int print_i,input_num;

        printf("0~999 사이의 검색 할 숫자입력:");
        scanf("%d",&input_num);

        if( input_num < 0 || input_num > 1000 ){
                printf("Check number['%d']:( 0 ~ 999 )\n\n",input_num);
                return -1;
        }

        SELECTION_SORT(ARR_NUM);

        print_i=BINARY_SEARCH(input_num,ARR_NUM);

        if(print_i>=0) printf(" 일치 결과 찾음 ARR_NUM[%d]: %d \n\n",print_i,ARR_NUM[print_i]);

        return 0;

}