[순환] 순환 알고리즘의 설계

순차 탐색 (Sequential Search)

아래 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다.
하지만 검색 구간이 시작 인덱스 0은 보통 생략한다.
즉 암시적 매개변수이다.

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

 

아래 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다.
즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.

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);
}

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

int search(int data[], int begin, int end, int target) { //binary search와는 다름
    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); //뒤쪽 검사
    }
}

 

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

	public static 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));
	}

	public static 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 (이진탐색)

자바 target.compareTo 함수
-> 자바는 기본적으로 오름차순을 기본으로 하기 때문에

왼쪽 수를 기준으로 오른쪽 수가 더 작으면 음수를, 

같으면 0을, 오른쪽 수가 더 크면 양수를 반환한다.

	public 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);
		}
	}

 

 

 

[무료] 영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 | 강의