#include "..\CookHeader.h"

Array <int> dataAry, sortedAry;
int searchCount = 0;

int seqSearch(Array <int> ary, int fData) {
	int pos = -1;
	for (int i = 0; i < len(ary); i++) {
		searchCount++;
		if (ary[i] == fData) {
			pos = i;
			break;
		}
	}
	return pos;
}

int binSearch(Array <int> ary, int fData) {
	int pos = -1;
	int start = 0;
	int end = len(ary) - 1;

	while (start <= end) {
		searchCount++;
		int mid = (start + end) / 2;
		if (fData == ary[mid])
			return mid;
		else if (fData > ary[mid])
			start = mid + 1;
		else
			end = mid - 1;
	}
	return pos;
}

int main() {
	int findData = 7878;

	randomInit(0, 999999);						// 0~999999
	for (int r = 0; r < 1000000; r++) {
		int num = cookRandom(gen); 
		dataAry.push_back(num);
	}

	int rndPos = cookRandom(gen);				// 임의의 위치
	insertArray(dataAry, rndPos, findData);		// 7878을 임의의 위치에 끼워 넣기
	copyArray(dataAry, sortedAry);				// 복사
	sortArray(sortedAry);						// 정렬

	// 일부만 출력
	Array <int> frontAry = { dataAry.begin(), dataAry.begin() + 5 };
	Array <int> rearAry = { dataAry.end() - 5, dataAry.end() };
	print("#비정렬 배열(100만개) -->");
	printArray_(frontAry);	print("~~~");	printArray(rearAry);
	frontAry = { sortedAry.begin(), sortedAry.begin() + 5 };
	rearAry = { sortedAry.end() - 5, sortedAry.end() };
	print("#정렬 배열(100만개) -->");
	printArray_(frontAry);	print("~~~");	printArray(rearAry);
	println("");

	int pos;
	searchCount = 0;
	pos = seqSearch(dataAry, findData);
	if (pos != -1) 
		println("순차 검색(비정렬 데이터) -->" + to_string(searchCount) + "회");

	searchCount = 0;
	pos = binSearch(sortedAry, findData);
	if (pos != -1) 
		println("이진 검색(정렬 데이터) -->" + to_string(searchCount) + "회");
}