이분탐색

이분 탐색 / 이진 탐색 (Binary Search)

이분 탐색 배열이 정렬되어 있어야 사용 가능 반으로 쪼개면서 탐색함 시간 복잡도 O(logN) (순차 탐색은 O(N)) 시작점, 중간점, 끝점을 가리키는 변수를 가짐 재귀, 반복문으로 구현 가능 1. 시작점, 중간점, 끝점 (left, mid, right) 정하기 2. 중간점과 찾는 값 비교 후 작으면 right를 mid-1로, 크면 left를 mid+1로 한 후 mid 값 다시 정하기 3. 2번을 반복 Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 이분 탐색으로 결정 문제를 해결하면서 범위를 줄여 최솟값, 최댓값을 찾음 결정 문제인지 아닌지의 차이 (이분탐색과) 1. left, mid, right를 정한 후 mid가 조건을 만족하는지 확인 2. 만족하지 않으면 mid 이전의 ..