이진검색

크기 10개의 배열을 난수로 받아 정렬이 되어 있지 않으면 정렬 한 후 
정렬된 정수 배열에 대해 이진 검색을 수행하여 주어진 정수의 인덱스를 반환하는 프로그램 
(난수로 발생된 배열에는 0이 들어가면 안되고, 중복된 수가 난수로 발생하면 안된다.
난수의 범위는 1~100까지로 한다.

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define MAX 10

int binarySearch(int[], int, int, int);

void swap(int *, int *);

void printArray(int[]);

int main(void)

{

int num[MAX];

int i=0, j=0, snum=0, lower=0, upper=MAX-1, index=0;

srand(time(NULL));

for(i=0; i<MAX; i++) 

{

num[i] = rand()%100; // 난수발생

if(num[i] == 0)  // 랜덤수중0을거름

i--;

for(j=0; j<i; j++) // 중복되는수발생금지

if(num[j] == num[i])

i--;

}

printArray(num);

// 버블정렬

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

for(j=MAX-1; j>i; j--) {

if(num[j-1] > num[j])

swap(&num[j-1], &num[j]);

}

}

printf("배열정렬>> \n");

printArray(num);

printf("\n검색할수를고르세요: ");

scanf("%d", &snum);

index = binarySearch(num, lower, upper, snum);

if(index>=0 && index<=MAX-1)

printf("찾는%d는배열의Index = %d 에있습니다. \n", snum, index);

else

printf("해당수를찾을수없습니다. \n");

return 0;

}

/* 이진검색*/

int binarySearch(int array[] , int lower, int upper, int target)

{

int center=0;

center = ((upper-lower)/2) + lower;

// 해당수를찾지못한경우

if(lower > upper)

return -1;

// 해당수를찾은경우

else if(array[center] == target)

return center;

else if(array[center] > target) {

upper = center - 1;

return binarySearch(array, lower, upper, target);

}

else {

lower = center+1;

return binarySearch(array, lower, upper, target);

}

//return 0;

}

/* 스왑함수*/

void swap(int *p, int *q)

{

int temp;

temp = *p;

*p = *q;

*q = temp;

}

/* 배열출력*/

void printArray(int array[])

{

int i=0;

printf("num[%d] = { ", MAX);

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

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

}

printf("} \n");

}