이분탐색

이분탐색 (Binary Search)

수열(주어진 배열) 에서의 탐색

• x가 존재하는지?
• x 이상, 이하, 등 의 원소는 몇개?

등의 조건을 탐색할 때의 시간복잡도 모두 O(N).

정렬된 수열에서의 탐색

-> 이분탐색

• 정렬이 보장되는 배열에서 기준원소를 가지고 범위를 이분하여 탐색

O(logN)