Binary Search (1) - 동작 방식

 

Binary Search 를 구현해 보겠다.

 

먼저 Binary Search란 

 

위의 그림처럼 배열의 중간값을 기준으로

 

찾고자 하는 값이 중간값보다 크면 기준의 오른쪽 배열을 선택, 찾고자 하는 값이 중간값보다 작으면 기준의 왼쪽 배열을 

 

선택해가며 원하는 숫자를 찾아내는 방법이다.

 

 

Binary Search에 대한 포스팅은

 

1. 사이즈가 10,000인 배열을 생성하고 배열에 겹치지 않는 랜덤한 숫자를 저장한 뒤 파일에 저장한다.

 

2. Binary Search를 Iterative한 방식으로 구현해 본다.

 

3. Binary Search를 Recursive한 방식으로 구현해 본 뒤 Iterative한 방식과 비교해 본다.

 

총 3개의 글로 나누어 포스팅 해 보겠다.

 

 

먼저 중복이 없이 오름차순으로 정렬된 10000개의 정수를 생성하여 data.txt 파일에 저장하였다.

 

처음에 랜덤하게 생성된 값을 기준으로 매번 이전값과 비교하여 이전값보다 클 경우에만 저장되는 방식으로 구현을 하려고

 

하였으나 이럴경우 처음 생성되는 기준값이 커질 수도 있고, 이전 값과 다음값의 차이가 엄청나게 클 수도 있는 문제점이 있었다.

 

 

따라서 간단하게 제일 첫번째 값은 무조건 1로 저장하고 이후 값부터는 이전값보다 최소 1에서 최대 3까지의 범위 내에서

 

플러스 되는 방식으로 10,000개의 정수를 생성해 보았다.

file = fopen("data.txt","r");

if(file==NULL) { // 파일을읽어올수없을때파일을작성한다.
			printf("파일이존재하지않으므로파일을생성합니다.\n");

			file = fopen("data.txt","w");

			arr[0] = 1; // 배열첫번째값은1을넣어줌
			fprintf(file,"%d ",arr[0]);

			for(i=1;i<arrSize;i++) {

				arr[i] = arr[i-1] + (rand()%3+1); 
				// 3 범위이내의값에서랜덤하게플러스시켜준다
				// 즉1부터시작하여1~3의범위내에서
				// 순차적으로커지는배열이생성된다.
				fprintf(file,"%d ",arr[i]);

			}

			printf("%d개의배열생성--- OK\n",arrSize);


		}

 

 

정수가 모두 생성된 뒤 data.txt 파일을 열어보면 10,000개의 정수가 오름차순으로 제대로 생성되어 있는 모습을 확인할 수 

 

있었다.