3-3장 검색 알고리즘 - 이진검색 (1/5)

 

해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다.

---

3-3장 검색 알고리즘 - 이진검색 (1/5)

이진검색

- 데이터의 키 값이 이미 오름차순 / 내림차순으로 정렬(sort)되어있어야 함

- 정렬이 되어있기 때문에 처음, 중간, 끝을 검색하며 범위를 줄여나가면 됨

- 선형 검색보다 좀 더 빠르게 검색할 수 있다.

 

이진검색 방법

- 찾는 값을 설정한다. (39).

- 배열의 중앙에 위치한 요소 a [5] (31)부터 검색 시작 (배열이 오름차순 / 내림차순으로 정렬되어 있기 때문에 찾는 값이 작으면 더 앞으로 가서 검색하고, 찾는 값이 크면 더 뒤로 가서 검색하면 된다.)

- 검색하려는 값인 39는 중앙 요소 a [5]보다 큼

- 검색 대상을 뒤쪽 5개 a [6] ~ a [10]로 범위가 좁혀감

- 검색 범위의 중앙에 위치한 요소 a [8] 68이 원하는 값인지 확인

- 찾는 값이 더 작으면 앞 a [6]~a [7]로 범위가 좁혀감

- 찾는 값이 더 크면 뒤 a [9] ~ a [10] 범위로 좁혀감

 

이진검색 성공과 실패

 

이진검색 범위

맨 앞 index : pl (left pointer)
중앙 index : pc (center pointer)
맨 끝 index : pr (right pointer)

a [pc] < key 일 때: a[pc+1] ~ a[pr] 검색
a[pc] > key 일 때: a [pl] ~ a [pc-1] 검색

 

이진검색 종류 조건

1. a [pc]와 key가 일치하는 경우
2. 검색 범위가 더 이상 없는 경우