이진탐색
n개의 요소를 가진 배열이 있을때, 특정한 key 값을 탐색하는 여러가지 방법이 있다.
가장 간단한 방법은 선형탐색을 하는 것이다.
- 이 방법의 시간 복잡도는 O(n) 이다.
- 순차적으로 자료를 탐색하는 방법이다.
또 다른 방법으로는 이진 탐색이 있다.
: 반복적으로 구간을 절반으로 나누며 탐색하는 방법
- 전체 배열의 절반을 기준으로 탐색을 시작한다.
- 만약, key 값이 전체 구간의 중간 값보다 작은 경우, 탐색해야 하는 구간은 중간 값 이하의 구간으로 감소한다.
- 그렇지 않다면 탐색 구간은 중간 값 이상의 구간이 된다.
- 탐색 구간이 비게 될 경우까지 반복적으로 탐색한다.
- 이진 탐색은 Divide and Conquer Algorithm 이다.
Binary search 는 information이 정렬된 경우에 시간 복잡도가 O(log n)이 된다.