재귀함수 (2)

순환 알고리즘 설계

적어도 하나의 basecase, 즉 순환되지 않고 종료되는 case가 있어야 한다.

모든 case는 결국 base case로 수렴해야 한다.

암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라.

• 순차탐색

int search(int[] data, int n, int target){
	for(int i=0; i<n; i++)
		if(data[i] == target)
			return i;
		return -1;
}

이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다.

하지만 검색 구간의 시작 인덱스 0은 보통 생략한다.

즉 암시적 매개변수 이다.

• 매개변수의 명시화 : 순차 탐색

int search(int[] data, int begin, int end, int target){
		if(begin > end)
			return -1;
		else if (target == data[begin])
			return begin;
		else 
			return search(data, begin+1, end, target);
}

이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다.

즉, 검색 구간의 시작점을 명시적(explicit)으로 지정한다.

이 함수를 search(data, 0, n-1, target)으로 호출한다면 앞 페이지의 함수와 완전히 동일한 일을 한다.

• 순차 탐색 : 다른 버전

이 함수의 비션은 data[begin] 에서 data[end] 사이에서 target을 검색한다.

즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.

int search(int[] data, int begin, int end, int target){
	if(begin > end)
		return -1;
	else if(target == items[end])
		return end;
	else
		return search(data, begin, end-1, target);
}

• 순차탐색 : 다른 버전

int search(int[] data, int begin, int end, int target){
	if(begin > end){
		return -1;
	}else{
		int middle = (begin + end) /2;
		if(data[middle] == target)
			return middle;
		int index = search(data, begin, middle-1, target);
		if(index != -1)
			return index;
		else 
			return search(data, middle+1, end, target);
	}
}

• 매개변수 명시화 : 최대값 찾기

int findMax(int[] data, int begin, int end){
	if(begin == end)
		return data[begin];
	else
		return Math.max(data[begin], findMax(data, begin+1, end));
}

이 함수의 미션은 data[begin]에서 data[end] 사이에서 최대값을 찾아 반환한다.

begin ≤ end라고 가정한다.

• 최대값 찾기 다른버전

int findMax(int[] data, int begin, int end){
	if(begin == end)
		return data[begin];
	else{
		int middle = (begin + end) / 2;
		int max1 = findMax(data, begin, middle);
		int max2 = findMax(data, middle+1, end);
		return Math.max(max1, max2);
}

• 이진 탐색

int binarySearch(String[] items, String target, int begin, int end){
	if(begin>end)
		return -1;
	else{
		int middle = (begin+end)/2;
		int compResult = target.compareTo(items[middle]);
		if(compResult == 0)
			return middle;
		else if(compResult <0)
			return binarySerach(items, target, begin, middle-1);
		else
			return binarySearch(items, target, middle+1, end);
	}
}

item[begin]에서 items[end] 사이에서 target을 검색한다.

이진 검색은 데이터들이 어떠한 조건에 의해 정렬되어 있어야 한다.