이진 검색

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용

 

이진 검색

 이 알고리즘은 데이터가 키값으로 이미 정렬(sort)되어있다 전제 조건이 필요하다.
이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다.

 

이진 검색 알아보기

아래와 같이 오름차순으로 정렬된 데이터에서 39를 검색하는 예시다.

int[] a = {5, 7, 15, 28, 29, 31, 39, 58, 68, 70, 95};

1. 먼저 배열의 중앙(10 / 2 == 5)에 위치한 요소인 a[5](값: 31)부터 검색을 시작.
2. 검색할 값인 39는 중앙 요소(a[5])보다 큼. 따라서 검색 대상을 뒤쪽의 5개(a[6] ~ a[10])로 좁힘.
   그리고 다음 검색 범위의 중앙에 위치한 요소인 a[8](값: 68) 선택한다.
3. 검색할 값인 39는 중앙요소 a[8]보다 작다. 다시 검색 대상을 앞쪽(a[6]~a[7])으로 줄인다. a[6]을 확인.

 검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정. 검색을 시작할 때 pl은 0, pr은 n - 1, pc는 (n - 1) / 2 이다. 

• a[pc] < key 일 때, a[pl] ~ a[pc] 는 key 보다 작은 것이 분명하므로 검색 대상에서 제외. 검색 범위를 중앙 요소 a[pc] 보다 뒤쪽인 a[pc + 1] ~ a[pr]로 좁힘. 이를 위해 pl 값을 pc + 1 로 업데이트.
• a[pc] > key 일 때, a[pc] ~ a[pr]은 key 보다 큰 것이 분명하므로 검색 대상에서 제외. 검색 범위를 중앙 요소 a[pc] 보다 앞쪽인 a[pl] ~ a[pc - 1]로 좁힘. 이를 위해 pr값을 pc - 1 로 업데이트.

위와 같은 과정을 반복하며 검색 대상을 찾음.

선형검색과 달리 순차적으로 진행되지 않으며, 범위를 지정하고 범위 내에서 중간값을 이용하여 탐색.