[알고리즘] 순차 검색 (Sequential Search) - JAVA / 자바

순차 검색 (Sequential Search, 선형 탐색 (Linear Search))

 - 일렬로 된 자료를 처음부터 마지막까지 순서대로 검색하는 방법

 - 가장 간단하고 직접적인 검색 방법

 - 배열이나 연결 리스트로 구현된 순차 자료 구조에서 원하는 항목을 찾는 방법

 - 검색 대상 자료가 많은 경우에 비효율적이지만 알고리즘이 단순하여 구현이 용이함

---

정렬되지 않은 순차 자료구조에서의 순차 검색

 - 검색 방법 : 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지 비교하여 찾음

    ㄴ 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지 반환 = 검색 성공

    ㄴ 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없음 = 찾은 원소가 없다 = 검색 실패

 

EX) List = {10, 3, 8, 29}

10

3

8

29

 

1. 9 검색

① 9 ≠ 10	10	3	8	29	② 9 ≠ 3	10	3	8	29
③ 9 ≠ 8	10	3	8	29	④ 9 ≠ 29	10	3	8	29

ANS = 검색 실패

2. 3 검색

① 3 ≠ 10

10

3

8

29

② 3 = 3

10

3

8

29

ANS = 1 (검색 성공)

 

 알고리즘 

sequentialSearch(list[], n, key)
    i ← 0;
    while (i < n and list[i] ≠ key) do {
    	i ← i+1;
    }
    if (i < n) then return i;
    else return -1;
end sequentialSearch()

 - 비교 횟수 : 찾고자 하는 원소의 위치에 따라 결정

    ㄴ 정렬되지 않은 원소에서의 순차 검색의 평균 비교 횟수 = 1/n(1+2+3+... + n) = (n+1)/2

 - 평균 시간 복잡도 : O(n)

---

정렬되어 있는 순차 자료구조에서의 순차 검색

 - 검색 방법

    ㄴ 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지 반환 = 검색 성공

    ㄴ 순서대로 검색하면서 키 값을 비교하여, 원소의 키 값이 찾는 키 값보다 커졌다 = 찾는 원소가 없다 = 검색 실패

 

EX) List = {3, 8, 10, 29}

3

8

10

29

1. 9 검색

① 9 > 3	3	8	10	29	② 9 > 8	10	8	8	29
③ 9 < 10	3	8	10	29

ANS = 검색 실패

2. 10 검색

① 10 > 3	3	8	10	29	② 10 > 8	3	8	10	29
③ 10 = 10	3	8	10	29

ANS = 2 (검색 성공)

 

 알고리즘 

sequentialSearch(list[], n, key)
    i ← 0;
    while (list[i] < key) do {
    	i ← i+1;
    }
    if (list[i] = key) then return i;
    else return -1;
end sequentialSearch()

 - 비교 횟수 : 찾고자 하는 원소의 위치에 따라 결정

    ㄴ 정렬되어 있는 원소에서의 순차 검색의 평균 비교 횟수 = 1/n(1+2+3+... + n) X 1/2 = (n+1)/4

    ㄴ 검색 실패의 경우 평균 비교 횟수가 절반으로 줄어듬.

 - 평균 시간 복잡도 : O(n)

---

< 분류 >

검색 방식 - 비교 검색(Comparison Search)

[자료구조] 검색 (Search)