이진탐색 알고리즘

출처: 이것이 코딩 테스트다 with Python 26강 이진 탐색 개요
https://www.youtube.com/watch?v=-Gx0T92-7h8&list=PLVsNizTWUw7H9\_of5YCB0FmsSc-K44y81&index=27

이진탐색이란?

• 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 시간복잡도: log2(n)

이진탐색

수도코드	이진탐색 예 - 원하는 값이 없는 경우
시작점 = 0 끝점 = list.length - 1 while(끝점 < 시작점) {   중간점 = (시작점 + 끝점) / 2    if (list[중간값] === 찾는값) {     return 중간값   } else if (list[중간값] > 찾는값) {     끝점 = 중간점 - 1   } else {     시작점 = 중간점 + 1   } return -1	이진탐색 예 - 원하는 값이 없는 경우

이진탐색 구현코드 

재귀적 방법

// 이진 탐색 - 재귀적 방법
function binary_search(arr, target, start, end) {
  // 끝점이 시작점보다 작으면 종료 - 리스트 안에 찾고자 하는 값이 없음
  if (end < start) {
    return -1;
  }

  const mid = Math.floor((start + end) / 2);

  // 찾은 경우, 중간값 인덱스 반환
  if (arr[mid] === target) {
    return mid;
  // 중간값이 더 크면, 왼쪽 확인
  } if (arr[mid] > target) {
    return binary_search(arr, target, start, mid - 1);
  // 중간값이 더 작으면, 오른쪽 확인
  } if (arr[mid] < target) {
    return binary_search(arr, target, mid + 1, end);
  }
}

반복문 방법

function binary_search_2(arr, target, start, end) {
  // 끝점이 시작점보다 작으면 종료 - 리스트 안에 찾고자 하는 값이 없음
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    // 찾은 경우, 중간값 인덱스 반환
    if (arr[mid] === target) {
      return mid;
      // 중간값이 더 크면, 왼쪽 확인
    } if (arr[mid] > target) {
      end = mid - 1;
      // 중간값이 더 작으면, 오른쪽 확인
    } if (arr[mid] < target) {
      start = mid + 1;
    }
  }

  return -1;
}

이진탐색 응용1 : 값이 특정범위에 속하는 데이터 구하기(bisect_left, bisect_right)

// bisect_left: 이진탐색리스트에 특정값이 들어갈 가장 왼쪽 위치를 반환
// bisect_right: 이진탐색리스트에 특정값이 들어갈 가장 오른쪽 위치를 반환

function count_by_range(arr, left_value, right_value) {
  const right = bisect_right(arr, right_value)
  const left = bisect_left(arr, left_value)
  
  return right - left
}

이진탐색 응용2: 파라메트릭 서치

• 최적화 문제를 결정문제(예 또는 아니오)로 바꾸어 해결하는 기법
  • 예시: 특정한 조건을 만족하는 가장 알맞는 값을 빠르게 찾는 최적화 문제
• 일반적으로 코딩테스트에서 파라메트릭 서치 문제는 이진탐색을 통해 해결할 수 있다

문제1: 떡볶이 떡 만들기

function test2(n, m, arr) {
  // 최댓값과 최솟값을 구한다
  let min = arr.reduce((a, b) => Math.min(a, b));
  let max = arr.reduce((a, b) => Math.max(a, b));
  let answer;
  
  while (min <= max) {
    // 중간값으로 떡볶이 떡의 길이를 구한다.
    const mid = Math.floor((min + max) / 2);
    const sum = arr.reduce((a, b) => {
      if (b >= mid) {
        return a + (b - mid);
      }

      return a;
    }, 0);

	// 떡볶이 떡의 길이가 작을 때는 자르는 크기를 줄이고
    if (sum < m) {
      max = mid - 1;
    // 떡볶이 떡의 길이가 크거나 같을 때, 자르는 크기를 늘린다.
    } else if (sum >= m) {
      answer = mid;
      min = mid + 1;
    }
  }
  
  return answer;
}

console.log(test2(4, 6, [19, 15, 10, 17]));

문제 2: 정렬된 배열에서 특정 수의 갯수 구하기

// 파라메트릭 서치 이용
function bisect_left(arr, value) {
  let start = 0;
  let end = arr.length - 1;
  let answer = 0;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    if (arr[mid] === value) {
      answer = mid;
      end = mid - 1;
    } else if (arr[mid] > value) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  return answer;
}

function bisect_right(arr, value) {
  let start = 0;
  let end = arr.length - 1;
  let answer = -1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    if (arr[mid] === value) {
      answer = mid;
      start = mid + 1;
    } else if (arr[mid] > value) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  return answer;
}

function test3(arr, value) {
  const right = bisect_right(arr, value);
  const left = bisect_left(arr, value);
  
  console.log(right, left)

  return right === -1 ? -1 : right - left + 1;
}

console.log(test3([1, 1, 2, 2, 2, 2, 3], 2))