Binary Search (2) - Iterative 방식으로 값 찾기

 

Binary Search (1) 에서 생성된 10,000개의 정수를 가지고 원하는 값을 찾아내는 함수를 구현하였다.

 

그리고 이 함수는 Iterative 방식, 즉 반복문을 통해 검색을 하는 방식으로 구현해 보았다.

int main(void)
{
        int arr[arrSize];

	int i=0, head=0;
	int searchNum;
	int searchCnt=0;
	int searchFlag = 0;

                        printf("파일 LOAD --- OK.\n찾고자 하는 수를 입력하세요 : ");
			scanf("%d",&searchNum);


			tStart = GetMicroSecond(); // microsec 측정 시작

			/////////////////////////////////////////////////////////////
			// Binary Search 함수 call후 리턴값으로 카운트 값을 받아온다.
			searchFlag = BinarySearch_iter(arr, searchNum, head, arrSize-1, &searchCnt); // iterative 방식
			/////////////////////////////////////////////////////////////

			tStart = GetMicroSecond() - tStart; // microsec 측정 종료

			if(searchFlag == 1)
			{
				printf("찾고자 하는 %d값을 %d번 비교해서 찾았습니다. (%d microsec)\n",searchNum, searchCnt, tStart);
			}
			else
			{			
				printf("찾고자 하는 %d값을 %d번 비교했지만 없었습니다. (%d microsec)\n",searchNum, searchCnt, tStart);		
			}

return 0;

}

searchFlag 라는 int형 변수에 함수를 달아 주었는데, 원하는 값을 찾았을 때에는 1을 return하고 값을 찾지 못했을 때에는 0을

 

return 하도록 함수를 만들어 주었다.

int BinarySearch_iter(int* _arr, int _searchNum, int _head, int _tail, int* _searchCnt)
{
	int mid=0;


	while(_tail >= _head)
	{
		mid = (_head + _tail) / 2;

		(*_searchCnt)++; // 카운트를 1씩 증가시켜준다.


		if(_searchNum > _arr[mid]) // 찾고자 하는 값이 중간값보다 클때
		{
			_head = mid + 1; // head값은 mid값 다음값부터 시작
		}
		else if(_searchNum < _arr[mid]) // 찾고자 하는 값이 중간값보다 작을때
		{
			_tail = mid - 1; // tail값은 mid값 하나 앞의 값으로 변경
		}
		else if(_searchNum == _arr[mid]) // 값을 찾았을때
		{
			//flag = 1;
			return 1; // 값이 찾아지면 1을 리턴한다
		}

	}

	return 0; // while을 다 돌고 나와서도 값을 찾지 못한 경우에는 값이 없는 경우이므로 0을 리턴한다.

}

 

 

함수 내에서 while문이 한번씩 돌 때 마다, 즉 비교를 한번씩 할 때마다 searchCnt를 1씩 증가시켜주고,

 

메인함수에서 넘겨받은 포인터 변수로 array의 head값과 tail값을 연산에 맞춰 변형 시켜가면서 연산을 해 주었다.

 

 

이렇게 구현한 함수를 이용하여 실제로 3930이라는 수를 검색해 보고 검색에 걸리는 시간을 측정해 보았다.

 

 

총 13번 비교과정을 통해 2 microsec가 소요되는 것을 확인할 수 있었다.