Sequential Search, Iterative and Recursive Search

문제 : Sequential search 알고리즘, iterative binary search, recursive binary search를 한 개의 프로그램 내에서 차례대로 작성한다. 각 알고리즘 마다 검색에 성공이면 해당 원소의 array index 번호를 출력하고, 실패하면 ‘-1’을 출력하게 하라.

• 단계 1. rand function 을 이용하여 오름차순으로 정렬된 양의 정수들을 생성하고, 이것을 array 에 저장한 뒤 화면에 출력한다.
  <단계 1 설명>
  1) Scanf 로 n, Min, Max 값 (n, Min, Max 는 모두 정수, n > 0, 0 < Min < Max)을 입력 받은 뒤, malloc 으로
  정수 n 개를 저장할 수 있는 array a[0]~a[n-1]을 생성한다.
  2) 생성되는 random number 가 Min 보다 크거나 같고 Max 보다 작거나 같아지도록 ‘rand 함수 사용
  예’의 알고리즘을 수정한다.
  3) array a[0]에 0 을 저장한 뒤, random number 로 n-1 개의 양의 정수를 생성하면서 이 값을 누적하여
  차례대로 array a[1]~a[n-1]에 저장한다. 예를 들어, a[0]=0 인 상태에서 random number 2 를 생성하면,
  a[1] = a[0]+2=2 가 되고, 이 상태에서 random number 1 을 생성하면 a[2] = a[1]+1 = 3, …과 같은
  방식으로 array 에 값을 저장한다.
  4) array a 에 저장된 정수들을 화면 출력한다.

---

참고 자료: rand 함수 사용 예
1) rand 함수 사용 시에는 ‘stdlib.h’를 include 해야 함.
2) rand 함수 수행 시 발생되는 난수의 범위는 0 ~ 32767 임. 중복되는 난수가 발생될 수 있음.

#include <stdio.h>
#include <stdlib.h>
#define num 100
int main()
{
	int i;
	for (i=0; i<num; i++)
		printf(“%d “, rand());
	return 0;
}

---

• 단계 2. Array a 에서 search 하려는 값을 scanf 를 이용하여 입력한다.
  (* 입력된 값이 -1 이 아니면 다음 단계를 수행, -1 이 입력되면 프로그램 수행을 중단한다.)
• 단계 3. Sequential search 알고리즘을 이용하여 search 한 뒤 성공이면, 해당되는 index 값을 출력하고,
  실패이면 -1 을 출력한다. 계산 시간을 출력한다.
• 단계 4. iterative binary search 알고리즘을 이용하여 search 한 뒤 단계 3 과 같은 방법으로 결과를
  출력한다 (switch 문과 직접 작성한 compare function 을 이용할 것). 계산 시간을 출력한다.
• 단계 5. recursive binary search 알고리즘을 이용하여 search 한 뒤 단계 3 과 같은 방법으로 결과를
  출력한다 (switch 문과 compare function 대신 if, else if, else 를 이용하여 작성할 것). 계산 시간을
  출력한다.
  단계 6. 단계 2 부터 다시 반복한다.

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
using namespace std;

class Search {
	int* a;
public:
	Search(int n, int* arr) {
		a = arr;
	}
	int seqsearch(int n, int m, int value) {
		clock_t start, finish;
		double elapsed;
		int i;

		start = clock();   //n부터m까지 순차탐색

		for (i = n; i <= m; i++)
			if (a[i] == value) {
				finish = clock();
				printf("sequential search result: %d ", i);

				elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
				printf("(%f", elapsed * 1000.0);
				printf("ms)\n");
				return i;
			}
		return -1;
	}
	int iterSearch(int n, int search) {
		clock_t start, finish;
		double elapsed;

		int left = 0;
		int right = n;
		int middle;

		start = clock();

		while (left <= right) {
			middle = (left + right) / 2;
			if (a[middle] == search) {
				finish = clock();
				printf("iterative binary search result: %d ", middle);
				elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
				printf("(%f", elapsed * 1000.0);
				printf("ms)\n");
				return middle;
			}
			else if (a[middle] > search)
				right = middle - 1;
			else
				left = middle + 1;
		}
		return -1;
	}
	int recBinarySearch(int left, int right, int search) {
		clock_t start, finish;
		double elapsed;

		start = clock();

		if (left > right) 
			return -1;
		int middle = (left + right) / 2;
		if (a[middle] == search) {
			finish = clock();
			printf("recursive binary search result: %d ", middle);
			elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
			printf("(%f", elapsed * 1000.0);
			printf("ms)\n");
			return middle;
		}
		else if (a[middle] > search) //중간값이 찾는값보다 크다면
			return recBinarySearch(left, middle - 1, search);
		else
			return recBinarySearch(middle + 1, right, search);
	}
};
int* arrGen(int n, int min, int max) {
	int *a;
	a = (int*)malloc(sizeof(int) * (n));
	a[0] = 0;
	printf("%d ", a[0]);
	for (int i = 1; i < n; i++) {
		a[i] = a[i - 1] + (rand() % (max - min + 1) + min);
		printf("%d ", a[i]);
	}
	printf("\n");
	return a;
}
int main() {
	int n, min, max, search;
	int stop = 0; int* arr;

	scanf_s("%d %d %d", &n, &min, &max);
	arr = arrGen(n, min, max);
	
	scanf_s("%d", &search);
	while (search != -1) {
		Search s(n, arr);

		s.seqsearch(0, n, search);
		s.iterSearch(n, search);
		s.recBinarySearch(0, n, search);
		scanf_s("%d", &search);
	}

	return 0;
}

main 속 scanf -> while -> scanf를 더 예쁘게 코딩할 방법이 있을 것 같다.