이진 탐색 성능
-
[알고리즘 개념] 이분 탐색 (Binary Search)알고리즘 공부/알고리즘 개념 2020. 9. 1. 15:20
이진 탐색 탐색이란 원하는 데이터를 배열 내에서 찾는 것이다. 이진 탐색은 정렬된 배열을 전제로 탐색하는 방법으로 한 번 비교할 때마다 절반의 데이터를 제외시킨다. 이러한 방법으로 엄청난 속도로 탐색을 완료할 수 있다. 예를 들어 70억 개의 데이터에 대해 순차 탐색은 평균적으로 35억 번을 비교하지만, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있다. 찾으려는 데이터와 중간 값을 비교하여 찾으려는 값이 중앙 값보다 작으면 왼쪽 데이터를 선택, 크다면 오른쪽 데이터를 선택하는 과정을 반복하며 데이터를 탐색한다. (중앙값) > (찾는 값) : 중앙 값 기준으로 왼쪽(작은 부분)을 탐색 (중앙값) < (찾는 값) : 중앙 값 기준으로 오른쪽(큰 부분)을 탐색 성능 이진 탐색의 성능을 계산해 보면 아..