3. 순환 알고리즘의 설계

• 적어도 1개의 base case, 즉 순환되지 않고 종료되는 case 있어야함

• 모든 case는 결국 base case로 수렴해야함

암시적 매개변수를 명시적 매개변수 로 바꿔라

순차 탐색

이 함수의 미션은 0~n-1 사이의 target을 검색 하지만 검색 구간의 시작 인덱스 0은 보통 생략. 즉, 암시적 매개변수 다.

• [0~n-1] 까지 검색할건데

  • 여기서 n-1은 매개변수 n으로 명시적 매개변수

  • 0은 암시적 매개변수. 암묵적으로 0부터 검색해야지

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

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

data[begin]에서 data[end] 사이에서 target을 검색 즉, 검색구간의 시작점을 명시적 으로 지정

int search(int [] data, int begin, int end, int target) {
    // 검색할 데이터의 개수가 0개라면 종료
    if(begin > end) {
        return -1;
    }
    else if (target==data[begin]) return begin;
    else return search(data, begin + 1, end, target);
}

0으로 암시 VS 시작 위치와 끝 위치를 명시

• recursion을 작성시 명시하는 것이 기본적인 원칙

• 어떤 배열데이터에 0~n-1 사이의 타겟을 찾음

순차 탐색: 다른 버전

뒤에서부터 비교 해보기

int search(int [] data, int begin, int end, int target) {
    // 검색할 데이터의 개수가 0개라면 종료
    if(begin > end) {
        return -1;
    }
    else if (target==data[end]) return end;
    else return search(data, begin, end - 1, target);
}

mid를 기준으로 0~mid-1 돌고 못찾으면 mid+1~e 돌기

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

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

int findMax(int [] data, int begin, int end) {
    // basecase는 데이터의 개수가 1개 일 때
    if(begin==end) return data[begin];
    else return Math.max(data[begin], findMax(data, begin + 1, 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);
    }
}

binary search

items[begin] 에서 items[end] 사이에서 target을 검색

이진 검색은 데이터가 정렬 되어있다는 전제

int binarySearch(String[] items, String target, int begin, int end) {
    // data 개수가 0개인 경우
    if (begin > end) {
        return -1;
    }
    else {
        int mid = (begin + end) / 2;
        int compareResult = items[mid].compare(target);
        if(compareResult == 0) {
            return mid;
        }
        else if(compareResult < 0) {
            return binarySearch(items, target, begin, mid - 1);
        }
        else {
            return binarySearch(items, target, mid + 1, end);
        }
    }
}