반응형 Binary Search1 이진탐색(Binary Search)와 Parametric Search 이진탐색(Binary Search)와 Parametric Search 1. 이진탐색1.1 기본 아이디어우리가 원하는 값을 찾고 싶을 때에는 정말 간단하게 생각하면, 모든 값들을 하나씩 보면서 맞는지 아닌지 확인는 방법이 직관적인 방법이라고 할 수 있다. 하지만 이렇게 찾는 것은 가장 마지막에 원하는 값이 있을 경우, 모든 값 들을 한번 씩 살펴보아야 하기 때문에, O(N)으로 볼 수 있다. 그렇다면 좀더 효율적인 방법은 없을까? 에서 시작한 것이 바로 이진탐색(Binary search)이다. 이진탐색(Binary search)의 경우는 결과적으로 보면 O(logN) 만에 원하는 값을 찾을 수 있는데, 그 이유는 정렬이 되있다는 가정이 있기 때문이다. 아래의 그림을 보면서, 왜 그러한지 직관적으로 이해를 .. 2016. 9. 13. 이전 1 다음 반응형
