이진탐색
[Search] Binary Search Tree (트리에서의 이진탐색)
01. 이진 탐색 트리 탐색 작업을 효율적으로 하기 위한 자료 구조 모든 원소는 서로 다른 유일한 키를 갖는다. key(왼쪽 서브트리) 루트노드의 키값)인 경우 : 루트노드의 오른쪽 서브트리에 대해서 탐색 연산 수행 서브트리에 대해서 순환적으로 탐색연산을 반복한다. 03. 탐색 성..
[Search] Binary Search (이진 탐색)
자료의 가운데에 있는 항목의 키값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법. 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함. 이진 검색을 하기 위해서는 반드시 자료가 정렬된 상태여야한다. 정의 자료의 중앙에 있는 원소를 고른다. 중앙 원소의 값과 찾고자 하는 목표값을 비교한다 목표값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로운 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다. 찾고자하는 값을 찾을때까지 1~3의 과정을 반복한다. 설명 간단하게 생각하면 소주 병뚜껑에 적힌 숫자로 UP&Down을 하는 것과 동일하다 일반적인 방법으로 숫자의 범위를 반씩 잘라가며 타겟이 ..