Binary Seach

파라매트릭 서치

Binary Search

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

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

문제 풀이

백준2805 나무자르기