공부/자료 구조 및 알고리즘
2019. 7. 13.
자료의 탐색 - 이진 탐색(Binary search)
이진 탐색(Binary search) 가운데에 있는 항목을 키값과 비교하여 다음 탐색 위치를 결정하여 키를 찾을 때까지 이진 탐색을 반복적으로 수행한다. ex) 순차 탐색과 달리 묶음 책 속의 수들이 차례대로 정렬되어 있는 구조를 가졌다는 전제를 토대로 책의 중간에 위치한 수를 먼저 비교하고 찾고자 하는 수가 비교한 수보다 큰 경우는 책의 오른쪽 부분을 탐색하고 작은 경우는 책의 왼쪽 부분을 탐색하는 것을 반복하는 방법. - 찾는 키값 > 원소의 키값: 오른쪽 부분에 대해서 이진 탐색 실행 - 찾는 키값 list[middle] ) return list[middle+1]부터 list[high]에서의 탐색; 이진탐색(Binary search) 예제 문제: 10장으로 구성된 묶음 책으로 각 장에 수가 다음과 ..