이진탐색

Minji Lee·2024년 1월 8일

Binary Search js 이진탐색

JS코딩테스트

목록 보기

46/122

순차 탐색 vs 이진 탐색

ex) 리스트에서 12인 원소의 위치 찾기

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인 → 시간 복잡도: O(N)

이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 → 시간 복잡도: O(logN)

이진 탐색 수행할 때 시작점(left)와 끝점(end)을 기준으로 탐색 범위 명시
각 단계마다 탐색 범위를 2로 나누는 것
이상적인 경우 매 단계마다 범위가 반으로 감소 → log 복잡도를 가짐
대표적인 사례
- 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우
- 데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우

이진 탐색 코드

재귀함수 이용

// 이진 탐색 소스코드 구현(재귀함수)
function 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);
}

ex) n(원소의 개수)와 target(찾고자 하는 값)

let n = 10;
let target = 7;
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

// 이진탐색 수행 결과 출력
let result = binarySearch(arr, target, 0, n - 1);
if (result == -1) console.log("원소가 존재하지 않습니다");
else console.log(`${result + 1}번째 원소입니다.`);

반복문 이용

// 이진 탐색 소스코드 구현(반복문)
function binarySearch(arr, target, 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;
  }
  return -1;
}

ex) n(원소의 개수)와 target(찾고자 하는 값)

let n = 10;
let target = 7;
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

// 이진탐색 수행 결과 출력
let result = binarySearch(arr, target, 0, n - 1);
if (result == -1) console.log("원소가 존재하지 않습니다");
else console.log(`${result + 1}번째 원소입니다.`);

정렬된 배열에서 특정 원소의 개수 구하기

코딩 테스트에서 정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산하는 것을 요구하는 경우 종종 존재

→ lowerBound()함수와 upperBound()함수 사용(이진 탐색 함수가 제공하는 기능)

lowerBound(arr, x): 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 왼쪽 인덱스 반환

// 정렬된 순서를 유지하면서 배열에 삽입할 가장 왼쪽 인덱스 반환
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;
}

동일한 값을 가지는 원소가 여러 개라면, 최대한 왼쪽으로 탐색 범위 이동
ex) lowerBound(arr, 2)→ 2 원소 찾기

upperBound(arr, x): 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 오른쪽 인덱스 반환

// 정렬된 순서를 유지하면서 배열에 삽입할 가장 오른쪽 인덱스 반환
function upperBound(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()

countByRange(): 정렬된 배열에서 값이 특정 범위에 속하는 원소의 개수 계산

// 값이 [leftValue, rightValue]인 데이터의 개수 반환하는 함수
function countByRange(arr, leftValue, rightValue) {
  // 유의: lowerBound와 upperBound는 end 변수의 값을 배열의 길이로 설정
  let rightIndex = upperBound(arr, rightValue, 0, arr.length);
  let leftIndex = lowerBound(arr, leftValue, 0, arr.length);
  return rightIndex - leftIndex;
}
// 배열 선언
let arr = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9];
// 값이 4인 데이터 개수 출력
console.log(countByRange(arr, 4, 4));
// 값이 [-1, 3] 범위에 있는 데이터 개수 출력
console.log(countByRange(arr, -1, 3));

파라메트릭 서치

이진 탐색 조건: 변경할(최적화할) 값 x에 대하여 f(x)가 단조 증가 혹은 단조 감소

단조 증가 함수: x ≤ y 이면 f(x) ≤ f(y) 인 경우
- 계단 형식 혹은 왼쪽보다 오른쪽 값이 더 큼
일반적으로 조건은 f(x)에 대해 정의됨

파라메트릭 서치: 최적화 문제를 결정 문제(예 or 아니오)로 바꾸어 해결하는 기법

ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능
예시 문제

예산(2512)

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.
1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
  
  예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.
  
  여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.
입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

작성한 코드
```
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let n = Number(input[0].split(" ")[0]); // 지방의 수(N)
let arr = input[1].split(" ").map(Number); // 각 지방의 예산 요청
let m = Number(input[2]); // 총 예산(M)

let start = 1; // 이진 탐색을 위한 시작점과 끝점 결정
let end = arr.reduce((a, b) => Math.max(a, b));

let result = 0;
// 이진 탐색 수행(반복문)
while (start <= end) {
  let mid = parseInt((start + end) / 2); // 현재의 중간점(상한액)
  let total = 0; // 배정된 예산의 총액 계산
  // 각 지방에서 요청한 예산을 하나씩 확인하며
  for (x of arr) {
    total += Math.min(mid, x); // 예산 배정
  }
  // 조건을 만족한다면, 상한액(최대화가 목표)을 증가시키기
  if (total <= m) {
    result = mid;
    start = mid + 1;
  }
  // 조건을 만족하지 못한다면, 상한액 감소시키기
  else {
    end = mid - 1;
  }
}
console.log(result);
```
풀이
- 문제 요구사항: 적절한 상한 금액을 찾는 것이 문제의 목표
1. 배정된 총 예산이 조건을 만족한다면, 상한 금액을 증가(최대화가 목표)시킴
2. 배정된 총 예산이 조건을 만족하지 못한다면, 상한 금액을 감소시킴

Minji Lee

이전 포스트

그리디 문제풀이(4)

다음 포스트