[이것이취업을위한코딩테스트다] chap07 - 이진 탐색

이진 탐색

 

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야 사용할 수 있는 알고리즘이다. 시작점, 끝점, 중간점을 활용하여 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적을 비교해 범위를 절반씩 좁혀가며 탐색하는 과정이다.

 

위와 같이 맨 처음 원소를 시작점, 마지막 원소를 끝점, 총 개수에서 2를 나눈 값을(소수점은 버린다) 중간점으로 둔다.

위와 같이 반씩 줄여가며 비교하다가 찾으려는 값과 중간점에 위치한 데이터가 같을 시 탐색을 종료한다. 절반씩 데이터가 줄어든다는 점으로 시간 복잡도는 O(logN)이다.

 

 

코딩 테스트에서의 이진 탐색

 

이진 탐색은 코딩 테스트에서 단골로 나오는 문제이고, 폭넓게 적용되기 때문에 난이도가 높고 구현할 코드량이 많아 실수하기 쉽다. 그래서 이진 탐색 코드를 암기하고 있는 것이 중요하다.

 

 

 

이진 탐색 트리

 

이진 탐색을 대용량 데이터베이스를 처리하기 위한 구조인 트리를 활용한 것이 이진 탐색 트리이다. 노드와 연결선으로 이루어져 있으며 다음과 같은 두 가지 특징을 가진다.

사진에서 보는 것과 같이

- 부모 노드보다 왼쪽 자식 노드가 작다.

- 부모 노드보다 오른쪽 자식 노드가 크다.

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 의 관계가 성립해야지 이진 탐색트리라 할 수 있다.

 

위와 같이 찾고자 하는 원소값 37이 있다면 37일을 부모 노드와 비교하면서 자식 노드로 진행하고, 다시 비교하며 값을 찾아가며 노드를 방문하는 형태로 얻을 수 있다.