반응형
프론트엔드 개발자는 가끔 자바스크립트로 문제를 풀어야한다. 하지만, 애처롭게도 c++에는 내장 라이브러리로 존재하는 binary_search, lower_bound, upper_bound가 존재하지 않느다. 따라서, 우리는 이분탐색을 "직접" 만들어야한다. 이분탐색에 대해 알아보자
Binary Search
const binarySearch =(arr, target)=>{
let left = 0;
let right = arr.length - 1;
while(left <= right){
let mid = Math.floor((left+right)/2);
if(arr[mid] === target){
return mid;
}else if(arr[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return -1;
}Lower Bound
const lowerBound =(arr, target)=>{
let left = 0;
let right = arr.length - 1;
while(left < right){
let mid = Math.floor((left+right)/2);
if(arr[mid] < target){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}- lower bound 는 배열에서 타겟값 이상이 처음으로 나타나는 위치를 찾는다.
- 이분탐색 하다가 target 값 이상인 left 값이 타겟값을 넘는 첫 위치다.
Upper Bound
const upperBound =(arr, target)=>{
let left = 0;
let right = arr.length - 1;
while(left < right){
let mid = Math.floor((left+right)/2);
if(arr[mid] <= target){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}- upper bound 는 배열에서 타겟값보다 큰 값이 나타나는 첫 위치를 찾는다.
- 타겟값을 초과하는 인덱스를 반환한다.
이분탐색 vs lower, upper
- 이분탐색은 탐색값을 찾는것 이므로 while의 조건이 left<=right다.
- lower, upper 는 탐색값의 바운더리를 찾는 것 이므로 while의 조건이 left < right다.
반응형
'Language > Javascript' 카테고리의 다른 글
| 코딩테스트를 위한 PriorityQueue (1) | 2024.10.31 |
|---|---|
| [JS] 프로토타입 (0) | 2024.09.29 |
