Binary Search는 이진 탐색입니다. 재귀함수를 쓰거나 반복문을 사용할 때에 반복되는 정도를 비약적으로 줄일 수 있기에 더 효율적으로 답을 구할 수 있습니다. 1~30의 숫자배열에서 7을 찾는다고 한다면 배열의 중간값과 7을 비교합니다. 중간값이 찾는값보다 크기에 중간값을 새로운 최대값으로 설정하고 다시 함수를 돌리는 형식으로 반복하면 그냥 반복문을 돌리는 것보다 더 빠르게 7을 찾을 수 있습니다.
또다른 예시를 들어보면 현재 코드스테이츠에서 푼 문제 중에 음식점에서 손님n명이 음식을 받는데 걸리는 시간의 최솟값을 리턴하는 문제가 있는데 상업 목적으로 배포된 문제를 무단으로 제가 말해버리면 위험하기 때문에 코드를 보여주기 보다는 로직을 글로 적어보겠습니다.
-
메뉴를 조리하는데 걸리는 시간들을 나열한 배열을 기준으로 가장 작은 값을 1로 잡고, 가장 큰값을 (인원수 * 가장 조리시간이 긴 메뉴 시간) 으로 잡습니다.
-
최솟값이 최댓값보다 커지기전 까지 while문을 돌린다. 중간값을 정하고 중간값을 한 메뉴마다 나누어서 한 메뉴당 먹을수 있는 최대 인원을 구합니다.
3.메뉴 하나마다 카운트를 해서 만약 정해진 인원을 넘기면 정해진 n명에게 음식을 주고도 시간이 남기 때문에 최솟값을 구하기 위해 시간을 줄일 필요가 있습니다. 그래서 중간값 - 1을 최대값으로 다시 정하고 다시 함수를 돌립니다. 그럼 더 작은 중간값에서 인원을 구할 수 있습니다. 해당 방식을 최솟값과 최댓값이 같아질 때 까지 반복문을 돌립니다.
https://github.com/alstjd8826