https://www.youtube.com/watch?v=k5A3HicbLec
-
Binary Search
중복된 데이터가 존재하는 배열을 탐색할 경우 좀 더 응용된 방법을 사용해야 한다. -
Lower Bound
key보다 크거나 같은 첫번째 값 -
Upper Bound
key보다 큰 첫번째 값
A{1,3,5,5,7,12,26,33,34} 있을 때
lowerBound(A, size, 5) = 5[2]
upperBound(A, size, 5) = 7[4]
lowerBound(A, size, 6) = 7[4]
upperBound(A, size, 30) = 33[7]
upperbound - lowerbound 하면 key 몇개 있는지 알 수 있다.
key 있는지 없는지 알고싶다면 lowerbound만 있어도 됨.
일반 bs는 값 찾으면 바로 리턴해서 loop 종료함.
but lb, ub는 값 찾았어도 loop 계속 돌아야 시작 위치, 끝 위치 찾을 수 있음.
따라서 일반 bs에서 해당 조건 빼야 함.
public static int binSearch(int[] arr, int key, int start, int end)
{
int middle;
while (start <= end)
{
middle = (start + end) / 2;
if (arr[middle] == key) // **
return middle; // ** 이 부분 빼서 1아니면 2에 더해줘야 함. ib, ub는 값이 어디에 더해지느냐에 따라 달라짐
else if (arr[middle] < key) // 1
start = middle + 1;
else // 2
end = middle - 1;
}
return -1;
}- Lower Bound
public static int binSearch(int[] arr, int key, int start, int end)
{
int middle;
while (start <= end)
{
middle = (start + end) / 2;
if (arr[middle] < key)
start = middle + 1;
else // 여기에 추가. mid가 key와 같아도(arr[mid] == key) 더 앞쪽에 같은값 있을 수 있으므로 end = mid - 1. 계속 loop 진행
end = middle - 1;
}
return start;
}- Upper Bound
public static int binSearch(int[] arr, int key, int start, int end)
{
int middle;
while (start <= end)
{
middle = (start + end) / 2;
if (arr[middle] <= key) // 여기에 추가. ub는 같은 값 찾아도 계속 뒤쪽으로 가야 함. 즉 start가 이동
start = middle + 1;
else
end = middle - 1;
}
return start;
}둘 다 start 리턴하는 이유는 조건문의 마지막 상태 생각하면 알 수 있다.
