이분검색

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int main() {

    int data[1000];

    int i, j, n=1000;

    int x, tmp, low, high, mid;

    srand(time(NULL));

    for(i=0;i<n;i+=1) {

        data[i]=rand();

    }

    //  Selection sort

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

        x = i;  // 가장 작은 수의 인덱스

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

            if(data[x]>data[j]) { x=j; }

        }

        // data[i]와  data[x]를 서로 바꾸어 준다.

        // 지금 찾은 리스트 중에서 가장 작은 원소를 data[i]에 넣는다.

        tmp=data[i];

        data[i]=data[x];

        data[x]=tmp;

    }    

    // 정렬한 자료를 출력한다.

    for(i=0;i<n;i+=1) {

        printf("%d ", data[i]);

    }

    printf("\n\n");

    // 사용자로 부터 수를 입력 받는다.

    scanf("%d", &x);

    // Binary Search 시작

    low=0;      // 낮은 인덱스

    high=n-1;  // 높은 인덱스

    while(low<=high) { // 낮은 인덱스가 높은 인덱스 이하일 경우에만 돈다.

        mid=(low+high)/2;  // 중간을 계산한다.

        if(data[mid]==x) { break; }  // 만약 찾았다면 while문을 탈출

        if(data[mid]<x) {     // 만약 찾는 값이 중간값보다 크다면

            low=mid+1;         // low를 mid+1로 주고 다시 시작한다.

        } else {                  // 만약 찾는 값이 중간값보다 작다면

            high=mid-1;         // high를 mid-1로 주고 다시 시작한다.

        }

    }

    // 만약 data[mid]가 찾는 값이면 찾았고, 아니면 못찾은 것이다.

    if(data[mid]==x) {

        printf("Found the key %d at %dth\n", x, mid);

    } else {

        printf("The key %d not found\n", x);

    }

    return 0;

}