Binary Seach

Binary Search

• Binary Search에서 주의해야할 점은 while(left<=right)에서 등호를 꼭 붙여야 하는 것입니다. 안 붙이게 되면, 원소가 하나 남았을 때 찾고자 하는 값과 남아있는 원소를 비교하지 않고 바로 while 문을 빠져나올 수 있기 때문에 꼭 등호를 붙여야 합니다.
• 반대로 부등호를 빼면 lower bound를 찾을 수 있을것
• click

// 재귀를 이용한 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;  // 값
}

lower bound

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 리턴
}

upper bound

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

파라매트릭 서치

• 최적화 문제를 결정 문제로 바꾸어 푸는것
• 최적화 문제란 문제의 상황을 만족하는 특정 변수의 최소값, 최대값을 구하는 문제
• 예) 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이분탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있음
• 문제 풀이: 백준2805 나무자르기