[자료구조] 순차탐색 이진탐색

소개글

1. 순차탐색
2. 이진탐색

각 탐색의 개념, 과정, 특성, 효율성 등

목차

1. 순차탐색
2. 이진탐색

본문내용

1. 순차탐색
① 순차탐색
- 파일에 저장된 데이터들을 따로 재구성 해야할 필요가 없으므로 가장 간단하게 구현할 수 있다.
- 임의의 순서대로 데이터들이 나열된 경우에는 유일한 탐색방법으로 사용
- 주어진 자료 파일에서 특정한 원소를 첫 번째 레코드부터 순차적으로 비교해 가면서 해당키 값을 가진 레코드를 찾아내는 가장 간단한 검색 방법이다.

② 특정 키를 찾기 위한 순차탐색의 과정
1. 파일의 첫 번째 레코드의 키와 찾고자 하는 값을 비교한다
2. 만일 레코드의 키와 찾고자 하는 값과 같다면 탐색을 종료한다
3. 레코드의 키와 찾고자 하는 값과 같지 않으면 다음 레코드로 이동하여 비교한다
4. 파일의 마지막 레코드의 키도 찾고자 하는 값과 같지 않다면 탐색을 종료한다

③ 순차탐색의 효율성 : n 개의 데이터가 저장되어 있는 파일로부터의 탐색
- 주어진 파일로부터 특정한 키를 찾을 때까지의 비교횟수로 나타냄
- 최악의 경우 : 찾기 원하는 키 x 가 파일의 마지막 레코드에 저장되어 있는 경우
⇒ n 번의 비교, O(n)

참고 자료

없음