[JAVA] 검색(1) - 순차 검색(선형 검색, Sequential Search)

0. 검색(Search)이란?

ㆍ여러 개의 데이터 안에서 원하는 데이터를 찾아내는 알고리즘

ㆍ탐색키(search key, 자료를 구별하여 인식할 수 있는 키)를 가진 항목을 찾는 것

ㆍ검색 종류 : 순차 검색(선형 검색, Sequential Search), 이진 검색(Binary Search)

 

1. 순차 검색(선형 검색, Sequential Search)

ㆍ일렬(배열)로 되어 있는 자료를 순서대로 검색하는 방법

- 가장 간단하고 직관적인 방법

- 순차구조로 된 자료구조에서 원하는 항목을 찾을 때 유용

- 단순하여 구현은 쉽지만, 검색 대상의 수가 많은 경우 수행시간이 증가하여 비효율적인 부분이 있음

 

2. 검색 과정

1) 정렬되어 있지 않은 경우 검색 과정

ㆍ첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 찾음

ㆍ키 값과 동일한 원소를 찾으면 그 원소의 인덱스를 반환

ㆍ자료구조의 마지막에 도달할 때 까지 검색 대상을 찾지 못하면 검색 실패

 

3. 순차 검색의 특징

순차 검색	정렬되어 있지 않은 경우	정렬되어 있는 경우(오름차순으로 정렬)
과정	첫 번째 원소를 찾으면 1 번 비교 두 번째 원소를 찾으면 2번 비교	자료를 순차적으로 검색하면 키 값을 비교 원소의 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 것으로 판단하여 검색을 종료
비교 횟수	찾고자 하는 원소의 순서에 따라 비교 횟수가 결정 평균 비교 횟수 : (n+1) / 2	찾고자 하는 원소의 순서에 따라 비교 횟수가 결정 정렬이 되어 있으므로,검색 실패를 반환하는 경우 비교 회수가 반으로 줄어듦
시간 복잡도	O(n)

 

4. 코드 예제