binary search는 탐색 방법중의 기초라고 할 수있을 정도로 쉽게 생각 할 수있고 거의 왠만한 개발하는 사람이라면 알고 있을 거라 생각하는데, 구현하려고 하면 조금 까다로운 부분이 있다.
이걸 글로 쓰게된 이유는 가끔씩 문제를 풀다보면 이분탐색 문제가 나오는데,
만족하는 특정 값 중에서 최소를 구하시오(under_bound), 최대를 구하시오(upper_bound)같은 형식으로 구해야하는 경우가 존재하는데 매번 풀때마다 헷갈린다.
따라서 정리를 해놓으려고 글을 작성한다.
기본적인 이분 탐색의 특징 (정렬되있어야하고, O(logN),,)은 가볍게 생략..
둘 다 key값이 존재하지 않는 경우 key값보다 큰 값 중 가장 작은 값을 반환한다.
즉, 존재하는 key값이 여러개일 경우 사용된다고 생각하면 된다.
// int target_val; <- target값
// int arr[N]; (오름차순으로 정렬되어있음)
int l =0;
int r = MAX_LENGTH-1; // index
// l가 r랑 같아질때 까지
while(l < r){
int mid = (l+r)/2;
if (arr[mid] <= target_val)
l = mid+1;
else
r = mid;
}
return l;
여기서 l을 반환하게 되는데 , 마지막에 l==r이 되면서 나오게 되는데,
index l에 있는 값은 key보다 첫번째로 큰 값을 나타낸다.
// int target_val; <- target값
// int arr[N]; (오름차순으로 정렬되어있음)
int l =0;
int r = MAX_LENGTH-1; // index
// l가 r랑 같아질때 까지
while(l < r){
int mid = (l+r)/2;
if (arr[mid] < target_![](https://velog.velcdn.com/images%2Fchangjunpyo%2Fpost%2Fd9bdfcee-1e45-4209-87eb-9ee2bcd9e84b%2Fharley-davidson-eeTJKC_wz34-unsplash.jpg)val) <= 여기 부분의 =만 바뀜
l = mid+1;
else
r = mid;
}
return l;
여기서 l을 반환하게 되는데 , 마지막에 l==r이 되면서 나오게 되는데,
index l에 있는 값은 key값보다 큰것 중 가장 작은 값의 index 가리키고 있다. 만약 없다면 key값보다 작은 것중에 하나 더 큰 것 이므로 key값보다 큰 가장 작은값.