검색

안녕하세요 : )

오늘은 검색알고리즘에 대해 알아보겠습니다.

 

1. 검색

저장되어 있는 자료 중에서 원하는 항목을 찾는 작업이다.

자료들은 각각을 구별하여 인식할 수 있는 키인 탐색키를 가진다.

 

1-1. 순차검색(Sequential Search)

일렬로 되어있는 자료를 순서대로 검색하는 방법이다.

리스트나 연결 리스트와 같은 순차구조로 구현된 자료구조에서 유용하다.

구현이 쉽다.

검색 대상이 많은 경우 수행시간의 증가로 비효율적이다.

정렬, 정렬을 하지않는 2가지 경우가 있다.

정렬되지 않은 자료의 검색과정

1. 첫번째 원소부터 순서대로 검색대상과 키값이 같은 원소가 있는지를 비교하여 찾는다.

2. 키값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환.

3. 자료구조의 마지막에 갈 때까지 검색대상을 찾지 못하면 검색실패.

평균 비교 횟수는 1/n(1+2+3+......n)=(n+1)/2