탐색 알고리즘
저장된 데이터들 중에 원하는 값을 찾는 알고리즘
대표적으로 아래와 같은 알고리즘들이 있다.
선형 탐색 알고리즘 (Linear Search Algorithm)
이진 탐색 알고리즘 (Binary Search Algorithm)
해시 탐색 알고리즘 (Hash Search Algorithm)
이분 탐색 알고리즘
미리 정렬된 탐색공간에서 탐색범위를 절반씩 나누어 가며 탐색하는 알고리즘
검색키가 60인 경우의 예시
관련 알고리즘 문제
프로그래머스 입국심사 문제
해당 문제는 심사대상자 n명과 심사관이 걸리는 시간을 나열한 times배열을 제공한다. 제공된 문제공간에서 입국심사를 끝낼 수있는 최소시간을 구하는 문제이다.
https://school.programmers.co.kr/learn/courses/30/lessons/43238
나의 풀이
탐색 공간을 모든 입국심사가 끝난 시간을 기준으로 두었다.
모든 심사 대상자들이 심사를 마치는 최소의 경우와 최대의 경우를 지정하고 이 두가지 경우의 중간값을을 이분 탐색의 중간값으로 두었다.
프로그래머스는 총 6명의 심사 대상자, 2명의 심사관(각 7분, 10분이 걸리는 심사관)의 경우를 예시로 들어준다.
이때 모든 심사 대장자들이 심사를 마칠 수 있는 최소의 시간은 1로 설정했다.(해당 예시의 경우에는 최소의 경우가 1보다 더 클 수있지만 일반적으로 한번에 모든 심사대상자가 심사될 수있는 경우를 고려)
최대 시간은 가장 오래동안 심사하는 심사관에게 n 명이 모두 심사를 받는 times의 마지막 요소 * n 으로 설정했다.
이 두가지 경우의 중간값을 이용하여 탐색해 나간다.
모든 심사관들이 중간값 시간동안 심사한 사람의 수를 확인해가며 탐색 범위를 좁혀간다.
(중간값 동안 심사한 사람의 수가 n보다 큰 경우 최대의 경우를 중간값 -1로, 작은 경우 최소의 경우를 중간값 + 1로둔다.)
최대의 경우가 최소의 경우보다 작거나 같을때 까지 반복하여 입국심사에 걸리는 최소 시간을 구한다.
