이진검색 알고리즘

이진검색 알고리즘

정렬된 배열에서 원하는 데이터를 찾는 이진검색입니다. 작은 것에서 큰것으로 정렬하는 법을 오름차순이라고 합니다. 처음부터 끝으로 갈수록 값이 점점 커지므로 언덕을 오르는것과 같습니다. 큰 것에서 작은것으로 정렬하면 내림차순이라고 합니다. 처음부터 끝으로 갈수록 값이 점점 작아지므로 언덕을 내려가는것과 같습니다.

여기서는 오름차순으로 정렬된 배열을 대상으로 이진 검색 알고리즘을 설명합니다. 이진 검색 알고리즘의 개요는 다음과 같다.

1. 찾는값이 같으면 인덱스를 표시하고 종료한다.

2. 찾는 값이 크다면 검색대상을 앞쪽으로 좁힌다.

3. 찾는 값이 작다면 검색 대상을 뒤쪽으로 좁힌다.

검색 대상이 없어질때까지 처리를 반복합니다.

여기서는 변수를 명시하지 않고 알고리즘의 개념을 먼저 설명한다. 다소 복잡한 알고리즘이기에 개념을 먼저 파악해야한다.

 

다음으로 이진 검색에 필요한 변수를 설명한다. 2장의 선형 검색과 마찬가지로 검색 대상, 찾아낼 값이 저장된 변수, 찾은 요서의 인덱스를 저장하는 변수가 필요하다.  pos의 초기값으로는 발견되지 않았음을 나타내는 -1을 저장한다.

또한 검색 대상의 왼쪽 끝 요소의 인덱스를 저장한 변수, 오른쪽 요소의 인덱스를 저장한 변수, 중앙 요소의 인덱스를 저장한 변수가 필요하다. 왼쪽은 0, 오른쪽은 9로 지정한다.