[자료구조]이진 탐색(Binary Search)
이진 탐색 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값을 비교하는 방식입니다. 선택한 중앙값을 기준으로 찾고자 하는 값보다 크다면 기준의 왼쪽 범위에서, 찾고자 하는 값보다 작다면 기준의 오른쪽 범위에서 다시 중앙값을 선택하여 반복합니다. 이진 탐색 과정을 그림으로 보자면 다음과 같습니다. 위 그림에서 보면 길이가 10인 리스트에 { 0,2,4,6,8,10,12,14,16,18 } 값이 정렬되어 저장되어 있고, 여기서 12를 찾는 과정입니다. 처음에 중앙값, (length / 2)인 5를 기준으로 합니다. 리스트의 5번 index의 값을 기준으로 하는 겁니다. 리스트의 5번 index의 값은 10으로 찾고자 하..
2018. 2. 14.
