이진검색(Binary search)

전제조건 : 데이터들이 정렬되어있어야함

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

void generate(int* ptr, int mod, int size) {
	int i;
	srand((unsigned int)time(NULL));
	for (i = 0; i < size; i++) {
		ptr[i] = rand() % mod + 1;
	}
}

void PrintArray(int* ptr, int size) {
	int i;
	for (i = 0; i < size; i++) {
		printf("%d ", ptr[i]);
	}
}

void Sort(int* ptr, int size) {
	int key;
	int i, j;
	//삽입정렬
	for (i = 1; i < size; i++) {
		key = ptr[i];
		for (j = i - 1; j >= 0 && ptr[j] > key; j--) {
			ptr[j + 1] = ptr[j];
		}
		ptr[j + 1] = key;
	}
}

int Binary_Search(int* ptr, int data, int size) {
	int pl, pc, pr;
	pl = 0;
	pr = size - 1;
	while (pl < pr) {
		pc = (pl + pr) / 2;
		if (data < ptr[pc]) {
			pr = pc - 1;
		}
		else if (data > ptr[pc]) {
			pl = pc + 1;
		}
		else if (data == ptr[pc]) {
			return pc;
		}
	}
	if (data == ptr[pl]) {
		return pl;
	}
	else {
		
		return -1;
	}
}

int main() {
	int size;
	int* arr = NULL;
	int mod;
	int data;
	printf("생성하고자 하는 배열의 요소의 개수를 정하시오\n");
	scanf("%d", &size);
	arr = (int*)calloc(size, sizeof(int));
	assert(arr != NULL);

	printf("배열의 요소들의 숫자 범위를 정하시오(1~입력한숫자)\n");
	scanf("%d", &mod);
	generate(arr, mod, size);

	printf("\n생성된 배열 요소 출력\n");
	PrintArray(arr, size);

	printf("\n배열 요소 오름차순으로 정렬\n");
	Sort(arr, size);
	PrintArray(arr, size);

	printf("\n찾고자 하는 숫자를 입력하시오\n");
	scanf("%d", &data);
	
	if (Binary_Search(arr, data, size) == -1) {
		printf("해당 데이터는 존재하지 않습니다\n");
		return;
	}
	else {
		printf("해당 숫자 %d는 배열 %d번째 요소(arr[%d])에 존재합니다", data, Binary_Search(arr, data, size), Binary_Search(arr, data, size));
	}






	getchar();
	return 0;
}