- at least 하나의 순환되지 않고 종료되는, base case 가 있어야한다.
- 모든 case 는 finally, base case 로 수렴해야 한다.
- implicit parameter 를 -> explicit parameter 명시적 로 바꾸어라.
sequential search
순차적
: int array 에서 0 ~ n (data 의 갯수) 까지 search 하다가, target 이면 그 위치 i 를 return 한다.
static int search(int[] data, int n, int target) {
for(int i=0;i<n; i++) {
if(data[i] == target)
return i;
}
return -1;
}
보면은 implicit parameter 이다.
이것을 explicit parameter 화 를 한다.
static 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);
}
}
> >
시작을 begin 으로, 끝을 end 로 표현했다.
begin [ ------------------- ] end
↓
[ target ]
base case 는 결국엔 끝나는 조건인데, begin 이 end 보다 커지면
갯수가 0 이 나온다 때문에 끝내야한다.
if(begin>end) {
return -1;
// 여기로 finally, 수렴하게 된다
}
begin 그러니까 0 부터 시작해서 ~ end ( 아까의 n ) 까지
하나씩 돌려보는 것이다.
0 -> 맞으면 return 하고 아니면 +1 -> 1 ,,,, -> 2 - > ... -> end
이런식으로 한다.
else if (target==data[begin]) {
return begin;
} else {
return search(data, begin+1,end,target);
}
- recursion 에서 explicit parameter 를 하는 이유는
그렇게 하지 않으면 밑에서의 시작구간이 달라지기 때문이다.
이 와 다른 version 이 있다.
end 로 뒤부터 search 해보는 것이다.
static int search(int[] data, int begin, int end, int target) {
if(end<0) {
return -1;
}
else if (target==data[end]) {
return end;
} else {
return search(data, begin,end-1,target);
}
}
findMax
- 최대값 찾기.
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));
}
}
Binary search
- 크기순으로 정렬되어있을때 쓸수있는 방법이다.
static 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 binarySearch(items,target,begin,middle-1);
else
return binarySearch(items,target,middle+1,end);
}
}