이분 탐색 Binary Search 이분 탐색의 개념과 특징 이분 탐색(혹은 이진 탐색)은 이미 정렬된 배열에 대해 log₂N의 평균 검색 길이를 갖는 매우 빠르고 간단한 알고리즘이다. 기본 알고리즘 구간에 대해 중간값을 우선 검사한다. 중간값보다 작다면 찾는 값은 왼쪽 구간에 있다. (right = mid-1) 중간값보다 크다면 찾는 값은 오른쪽 구간에 있다. (left = mid+1) 중간값과 같다면 종료 구간을 줄여가며 1~3을 반복한다. 예제 정렬된 배열에 대해 목표값 9를 찾고자 한다. Search 1. left = 0(인덱스 위치) right = 8 mid = (0+8)/2 = 4 >>7(중간값)은 목표값 보다 작으므로 구간을 오른쪽으로 옮긴다. >>left = mid + 1 Search 2...
