검색알고리즘_순차탐색

검색알고리즘

검색이란?

특정한 구조로 구성되어 있는 자료의 집합에서 주어진 키에 해당하는 레코드를 찾아내는 것

단순히 자료를 찾는 것에만 국한되는 것이 아니라 자료가 새로 추가되고 삭제될 때 어떻게 이 자료들의 특정한 구조를 계속 유지하느냐하는 문제도 포함되어있다.

 

순차검색(선형검색)

주어진 자료 파일에서 처음부터 검색키에 해당하는 레코드를 순차적으로 비교하여 찾는 가장 단순한 검색 방법

장점 : 데이터를 따로 조작할 필요가 없어 단순

단점 : 리스트의 길이가 길면 비효율

시간의 복잡도 : O(n)

 

1. 별다르게 조직화가 필요없다.

2. N개의 자료에 대해서 평균적으로 N/2번의 비교를 해야한다.

검색

[검색 방법]

① 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다.

② 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환한다.

③ 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이므로 검색 실패

 

개선 :검색한 키를 선두로 옮기는 과정

 

삭제

[삭제 방법]

① 삭제하려는 키가 어디에 있는지 탐색한다.

② 찾으려는 키가 나올때 까지 한칸씩 당기고 배열의 자료수를 하나 감소 시킨다

 

삽입

[삽입 방법]

① 배열의 인덱스를 하나 증가하고 배열의 제일 뒤에 key를 덧 붙인다.

② 그런 뒤 삽입위치를 리턴