Binary Seach - GitDeveloperKim/DreamEach GitHub Wiki

// 재귀를 이용한 binary search
public static int binarySearch (int [] arr, int start, int end, int value) {
        int result = 0;
	int mid = (start+end)/2;
	if (value == arr[mid]) {
		result = arr[mid];
	} else if (value < mid) { 
           	result = binarySearch (arr,start, mid-1,value);
	} else if (value > mid) {
		result = binarySearch (arr,mid+1, end,value);
	} 
	return result;
}

// while 을 이용한 binary search
private static int binarySearch_while (int s, int e, int target) {
        int index = -1;
        // 등호 기호가 들어가야한다
	while (s <= e) {
		int mid = (s+e)/2;
                // target 찾고자 하는 값, dp[mid] 배열에서 중앙값
                if (target == dp[mid]) {
                    return mid; // 찾음
		else if (target < dp[mid]) {
		    e = mid;   // 좌측 탐색
		} else if (target > dp[mid]){
		    s = mid+1; // 우측 탐색
		}
	}
	return index;  // 값
}

private static int lower_bound (int s, int e, int target) {
	while (s < e) {
		int mid = (s+e)/2;
                // target 찾고자 하는 값, dp[mid] 배열에서 중앙값
		if (target <= dp[mid]) {
			e = mid;
		} else {
			s = mid+1;
		}
	}
	return e;  // end 리턴
}

private static int upperBound(List data, int target) {
    int begin = 0;
    int end = data.size()-1;
    
    while(begin < end) {
    	int mid = (begin + end) / 2;
        // 타겟 값 보다 search 값이 작거나 같다면
        if(data.get(mid) <= target) {
        	begin = mid + 1;
        }
        else {
        	end = mid;
        }
    }
    return end;
}