이것이 코딩테스트다 챕터 7 이진탐색

순차 탐색

말 그대로 리스트나 배열의 앞에서부터 원하는 아이템을 찾는 방식

순차 탐색 방식

이진 탐색(Binary Search)

탐색 범위를 절반으로 줄이며 아이템을 찾는 방식.

배열 내부의 데이터가 정렬되어 있어야 사용 가능하다

시작점,끝점,중간점을 조절하며 아이템을 찾는다

초기 시작점은 배열의 첫 인덱스(0), 초기 끝점은 배열의 마지막 인덱스, 중간점은 항상 시작점과 끝점의 절반

아이템을 찾거나 배열에 아이템이 없다고 판단될 때까지 반복한다.

이진 탐색 방식

이진 탐색 트리(Binary Search Tree, BST)

트리 자료구조 중 특정한 특징을 가진 트리.

이진 탐색 트리의 특징

• 모든 노드는 2개 이하의 자식 노드를 가진다
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드를 만족시킨다

BST의 예시