binary search (1) 썸네일형 리스트형 38. Binary Search 이분 탐색(이진 탐색, Binary Search)은 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있는 탐색 방법이다. 기본적인 원리는 정렬된 데이터를 앞쪽 절반과 뒤쪽 절반으로 나눈 다음 두 구간 중 해당 값을 포함하지 않는 구간을 배제하고 남은 한 구간에서 다시 데이터를 찾는 과정을 반복하는 것이다. 이렇게 하다가 구간에 값이 하나 남았을 경우 그 값을 찾는 값과 비교해서 같다면 원하는 값을 찾은 것이고, 다르다면 데이터에 원하는 값이 존재하지 않는 것이다. 데이터의 수가 $n$일 때 이분 탐색의 시간복잡도는 $O(\text{lg }n)$이다. BOJ 1920. 수 찾기 (Silver IV) 이 문제를 통해서 이분 탐색을 더 자세히 이해할 수 있다. 일단 $n$개의 정수를 정렬하고, 찾으려는 각각의 .. 이전 1 다음
