211207

Posted on In

211207

알고리즘

이진탐색 템플릿

1
2
3
4
5
6
7
const binarySearch(arr, target, start, end) {
if (start > end) return -1;
let mid = parseInt((start + end) / 2);
if (arr[mid] == target) return mid
else if (arr[mid] > target) return binarySearch(arr, target, start, mid -1);
else return binarySearch(arr, target, mid + 1, end);
}

반복문으로 왠만하면 반복문이 빠름

1
2
3
4
5
6
7
8
function binarySearch(arr, tareget, start, end) {
  while (start <= end) {
    let mid = parseInt((start + end) / 2);
    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) end = mid - 1;
    else start = mid + 1;
  }
}

lowerBound(a, x) 하한선 → 정렬된 데이터가 있을때 정렬을 유지하면서 배열 a 에 x를 가장 왼쪽에 넣을 인덱스 반환

upperBound(a, x) 상한선 → 정렬 유지하면서 배열 a 에 가장 오른쪽에 넣을 인덱스 반환

lowerBound:

1
2
3
4
5
6
7
8
function lowerBound(arr, target, start, end) {
	while(start < end) {
		let mid = parseInt((start + end / 2);
		if (arr[mid] >= target) end = mid;
		else start = mid + 1;
	}
	return end
}

uppserBound :

1
2
3
4
5
6
7
8
function lowerBound(arr, target, start, end) {
	while(start < end) {
		let mid = parseInt((start + end / 2);
		if (arr[mid] > target) end = mid;
		else start = mid + 1;
	}
	return end
}

countByRange : 같이 사용하는 것

1
2
3
4
5
function countByRange(arr, leftValue, rightValue) {
  let rightIndex = upperBound(arr, rightValue, 0, arr.length);
  let leftIndex = lowerBound(arr, leftValue, 0, arr.length);
  return rightIndex - leftIndex;
}

보통 3가지중 하나

  1. 단순 이진 탐색
  2. countByRange
  3. 파라메트릭 서치 → 이진탐색이 아닌거 같지만 이진탐색인걸 찾아야 함. (예 혹은 아니오로 )