ch01. 윤성우의 열혈 자료구조 1장 예제 소스코드

윤성우의 열혈 자료구조는 자료구조에 대한 기본을 배울 수 있는 개론서입니다. 다양한 그림을 사용하여 자료구조를 친절하게 설명하였으며 독자들에게 예제 코드를 제공하기 때문에 학습하기 용이합니다. 더불어 학습의 완성도를 높이는 다양한 문제와 그 답안을 제공하여 자료구조를 완벽히 익히는 데 도움이 되는 자료구조 개론서입니다.

 

#include <stdio.h>

int BSearch(int ar[], int len, int target)
{
	int first=0;   // 탐색 대상의 시작 인덱스 값
	int last=len-1;   // 탐색 대상의 마지막 인덱스 값
	int mid; 

	while(first<=last)
	{
		mid=(first+last)/2;   // 탐색 대상의 중앙을 찾는다. 

		if(target==ar[mid])   // 중앙에 저장된 것이 타겟이라면
		{
			return mid;
		}
		else    // 타겟이 아니라면 
		{
			if(target<ar[mid])   
				last=mid-1;   // 뒷부분을 탐색 대상에서 제외
			else
				first=mid+1;   // 앞부분을 탐색 대상에서 제외
		}
	}
	return -1;   // 찾지 못했을 때 반환되는 값 -1
} 

int main(void)
{
	int arr[]={1, 3, 5, 7, 9};
	int idx;

	idx=BSearch(arr, sizeof(arr)/sizeof(int), 7);
	if(idx==-1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	idx=BSearch(arr, sizeof(arr)/sizeof(int), 4);
	if(idx==-1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

 

#include <stdio.h>

int BSearch(int ar[], int len, int target)
{
	int first=0;
	int last=len-1;
	int mid; 
	int opCount=0;   // 비교연산의 횟수를 기록

	while(first<=last)
	{
		mid=(first+last)/2;

		if(target==ar[mid])
		{
			return mid;
		}
		else 
		{
			if(target<ar[mid])   
				last=mid-1;
			else
				first=mid+1;
		}
		opCount+=1;   // 비교연산의 횟수 1 증가
	}
	printf("비교연산 횟수: %d \n", opCount);  // 탐색 실패 시 연산횟수 출력
	return -1;
} 

int main(void)
{
	int arr1[500]={0,};    // 모든 요소 0으로 초기화
	int arr2[5000]={0,};    // 모든 요소 0으로 초기화
	int arr3[50000]={0,};    // 모든 요소 0으로 초기화
	int idx;

	// 저장되지 않은 정수 1을 찾으라고 명령
	idx=BSearch(arr1, sizeof(arr1)/sizeof(int), 1);
	if(idx==-1)
		printf("탐색 실패 \n\n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	// 저장되지 않은 정수 2를 찾으라고 명령
	idx=BSearch(arr2, sizeof(arr2)/sizeof(int), 2);
	if(idx==-1)
		printf("탐색 실패 \n\n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	// 저장되지 않은 정수 3을 찾으라고 명령
	idx=BSearch(arr3, sizeof(arr3)/sizeof(int), 3);
	if(idx==-1)
		printf("탐색 실패 \n\n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

 

#include <stdio.h>

int LSearch(int ar[], int len, int target)
{
	int i;
	for(i=0; i<len; i++)
	{
		if(ar[i]==target)
			return i;    // 찾은 대상의 인덱스 값 반환
	}
	return -1;    // 찾지 못했음을 의미하는 값 반환
}

int main(void)
{
	int arr[]={3, 5, 2, 4, 9};
	int idx;

	idx=LSearch(arr, sizeof(arr)/sizeof(int), 4);
	if(idx==-1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	idx=LSearch(arr, sizeof(arr)/sizeof(int), 7);
	if(idx==-1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}