Binary Search (recursive)

1. Problem

- 크기가 n인 정렬된 배열 S에서 x를 찾아보자

 

2. Input

1) 양수 n

2) 오름차순으로 정렬된 S indexed from 1 to n

3) key x

 

3. Output

1) x의 위치

2) S에 x가 없다면 0

 

4. PseudoCode

index location(index low, index high){
    index mid;
    if(low>high)
        return 0;
    else{
        mid = floor((low+high)/2);
        if(x==S[mid])
            return mid;
        else if(x<S[mid])
            return location(low,mid-1);
        else
            return location(mid+1,high);
    }
}

 

5. Example

class Test {
    public static void main(String[] args){
    	int[] arr = {10,12,13,14,18,20,25,27,30,35,40,45,47}; // 중앙값: 25
    	int a = 18;
    	System.out.println(a + "의 위치: " + location(0, arr.length-1, arr, a)); // 18의 위치: 5
    } // 비교 순서
    // 25 -> 13 -> 18
    
    static int location(int low, int high, int[] S, int x) {
    	int answer;
    	if(low>high) answer = 0;
    	else {
    		int mid = (low+high)/2;
    		if(x==S[mid]) answer = mid+1; // 실제는 0-indexed, 문제에서 요구하는 것은 1-indexed
    		else if(x<S[mid]) answer = location(low,mid-1, S, x);
    		else answer = location(mid+1,high, S, x);
    	}
    	return answer;
    }
}

- worst T(n) = lg 2 + 1