검색알고리즘_이분탐색

이분검색

이미 정렬된 배열에 대해서 검색하는 알고리즘이다. 순차 검색과 달리 자료를 정렬이라는 방법으로 조직한다. 그래서 검색은 간단하지만 자료를 삽입하거나 삭제할 때는 자료의 구조를 깨뜨리지 않아야 하는 어려움이 있다.

 

이분검색방법

1. 자료의 집합은 크기순으로 정렬되어 있어야한다.

2. 이미 정렬된 자료 집합에 대해 이분 검색법은 자료의 중간값을 우선 검사한다. 이 자료의 중간값이 찾는 키값이 아니라면 중간값과 키값의 크기를 비교하여 왼쪽 구간이나 오른쪽 구간을 선택한다.

3. 그리고 그 구간에 대해서 똑같은 방법으로 중간값과 키값의 크기를 비교한다.

검색

[탐색 방법]

① 구간의 중간값을 구한다.

② if(중간값 < 키값) 오른쪽 구간또는 왼쪽 구간을 선택한다.

삽입

 

[삽입 방법]

① key가 들어갈 위치를 찾는다.

② 삽입할 공간을 만든다

③ 공간에 자료를 삽입하고 자료수를 증가시킨다.

 

삭제방법은

순차검색알고리즘 삭제방법과 동일

이분 검색은 삽입과 삭제의 어려움 때문에 삽입과 삭제가 적은 거의 고정적인 자료집합에 유리하다.