오늘의 공부

이분탐색

이진탐색

처음부터 하나하나 값을 비교하는 순차탐색과 달리 이분탐색은 데이터를 찾을 때 검색 대상의 데이터를 반 씩 줄여나가면서 자료를 찾는 방법을 말한다.

◎ 이진탐색?

이분탐색에는 중요한 조건이 있는데, 바로 데이터가 정렬된 상태여야 한다는 것이다.

왜일까?

이분탐색은 데이터를 반씩 줄여 나가는 방식은 다음과 같다.

총 n개의 데이터가 있다고 했을 때

1. 중심 값(mid = (n+1)/2)을 잡는다

2. 중심 값(mid)과 찾으려는 값(value)을 비교.

3-1. mid == value => 탐색 종료. value의 값은 mid

3-2. mid > value => 중심값을 기준으로 왼쪽 값을 기준으로 다음 탐색을 진행한다. 즉 오른 쪽의 데이터는 더 이상 확인하지 않는다.

3-3. mid < value => 중심값을 기준으로 오른쪽 값을 기준으로 다음 탐색을 진행한다. 즉 왼쪽의 데이터는 더 이상 확인하지 않는다. 

4. 데이터가 1개 남을 때까지 반복한다. 

이렇게 7개의 데이터를 가진 배열이 있을 때 5를 찾고 싶으면 우선 배열의 가장 가운데 값을 기준으로 잡는다.

그 다음 찾으려는 값이 가장 가운데 값과 같으면 탐색이 끝나는 것이고 크면 오른쪽, 작으면 왼쪽을 확인한다.

5를 찾고 싶으니 중심인 4를 기준으로 오른쪽 값을 비교할 것이다. 그러면 1,2,3은 더 이상 비교하지 않아도 되므로 다음 탐색에서는 대상이 3개로 줄어들게 된다.

이런식으로 비교할 데이터가 1개가 남을 때까지 반복한다. 

계속 탐색 대상의 데이터를 반으로 줄여나가므로 이분탐색의 시간 복잡도는 O(logn)이 된다. 

◎ 라이브러리

#include <algorithm> 헤더를 추가하면 이미 구현된 이분 탐색을 사용할 수 있다.

iterator의 begin값과 end값, 찾을 value값을 순서대로 넣어주면 사용이 가능하다.