이진 탐색(Binary Search)

순차 탐색과 이진 탐색

순차 탐색(Sequential Search)

데이터가 담겨있는 리스트를 앞에서부터 하나씩 살펴보아서 원하는 데이터를 찾는 방법이다.

• 시간 복잡도: O(n)

const sequentialSearch = (list, search) => {
  for (let listItem of list) if (listItem == search) return true;
  return false;
};

이진 탐색(Binary Search)

정렬된 배열에서 특정 값을 찾는 알고리즘을 의미한다.

이진탐색은 탐색 범위를 절반씩 줄여나가기 때문에 선형탐색에 비해 빠른 속도를 보장한다.

하지만 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요하다.

• 시간 복잡도: O(logn)

---

이진 탐색 과정

이진 탐색을 수행할 때는 시작점(left)와 끝점(right)을 기준으로 탐색 범위를 명시한다.

left: 시작점
right: 끝점
mid: left와 right 중간 지점

1. 정해진 시작점(left)과 끝점(right) 범위의 중간값(mid)과 찾으려는 값을 비교한다.

2. 중간값(mid)에 따라 다른 과정 실행

   case a. 중간값(mid)이 찾으려는 값보다 큰 경우, 끝점(right)을 중간값(mid) -1 으로 옮긴다.

   case b. 중간값(mid)이 찾으려는 값보다 작은 경우, 시작점(left)을 중간값(mid) +1 으로 옮긴다.

3. right가 left보다 작아질때까지 반복

---

이진 탐색 코드 예시

반복문

// 이진 탐색 소스코드 구현(반복문)
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;
}

// 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) {
  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);
}

// 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}번째 원소입니다.`);

---

이진 탐색 알고리즘 예시

이진 탐색은 다음과 같은 사례에서 효과적으로 사용할 수 있다.

1. 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우

2. 데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우

💡 문제 확인

국가 예산 485를 지역 별 요청 금액 120, 110, 140, 150에 분배한다고 한다.

• 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.

• 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

위의 경우 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

💡 예산 문제의 해법

적절한 상한 금액을 찾는 것이 문제의 목표다.

국가 예산을 넘지 않는 선에서 상한 금액을 조절하여 최대한 지방에 분배할 수 있도록 한다.

💡 예산 문제 해결 코드

let area = [120, 110, 140, 150];
let money = 485;

let left = 1;
let right = Math.max(...area);
let answer = 0;

// 이진 탐색 수행
while (left <= right) {
  let mid = parseInt((left + right) / 2); // 상한 금액
  let total = 0; // 배정된 예산의 총액 계산
  for (let i = 0; i < area.length; i++) {
    total += Math.min(area[i], mid); // 상한 금액과 요청 금액 중 작은 것을 배정
  }

  if (total <= money) {
    // 상한액(최대화가 목표)을 증가시키기
    answer = mid;
    left = mid + 1;
  } else {
    // 상한액을 감소시키기
    right = mid - 1;
  }
}
console.log(answer); // 127

---

특정 범위에 해당하는 원소의 개수: 하한선과 상한선 함수

정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산할 때 사용할 수 있다.

하한선 함수(lowerBound)

정렬된 순서를 유지하면서 배열 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;
}

상한선 함수(upperBound)

정렬된 순서를 유지하면서 배열 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;
}

특정 범위에 해당하는 원소의 개수

앞에서 정의한 upperBound(), lowerBound() 함수를 이용하여 특정 범위에 해당하는 원소의 개수를 출력해보자.

// 배열 선언
let arr = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9];
let rightIndex = 0;
let leftIndex = 0;

// 값이 4인 데이터 개수 출력
rightIndex = upperBound(arr, 4, 0, arr.length);
leftIndex = lowerBound(arr, 4, 0, arr.length);
console.log(rightIndex - leftIndex); // 2

// 값이 [-1, 3] 범위에 있는 데이터 개수 출력
rightIndex = upperBound(arr, 3, 0, arr.length);
leftIndex = lowerBound(arr, -1, 0, arr.length);
console.log(rightIndex - leftIndex); // 6-0=> 6

---

📑 참고 자료

[YS’s develop story:티스토리]