순차 탐색 (Liner Search)

순차 탐색 (Liner Search)

✐ 개념

데이터를 순차적으로 하나씩 검색하여 찾는 방법 (선형 탐색)

✐ 시간 복잡도 : T(n) = O(n)

✐ Java 코드

public static int linerSearch(int[] data, int n, int target) {
    if(n < 0)
        return -1;
    
    else if(data[n] == target)
        return n;
 
    else
        return linerSearch(data, n-1, target);
}

✐ 코드 해석

✓ data = { 20, 15, 43, 66, 54, 100, 97 }

           위와 같이 크기가 7인 배열의 예시가 있다.

✓ n은 배열의 크기이므로 n의 값은 6이다. (n = 6)

           (배열의 인덱스는 0부터 시작한다.)

✓ target은 찾고자 하는 값이므로 43을 예로 든다. (target = 43)

▪︎ 첫 번째 탐색

▫︎ (2번 라인) n = 6이므로 if(n < 0) 조건 불일치

▫︎ (5번 라인) else if(data[6] == target) 결과 값이 (97 != 43)이므로 조건 불일치

                   ☛ { 20, 15, 43, 66, 54, 100, 97 } != { 43 }

▫︎ (9번 라인) 재귀 함수 실행 : linerSearch(data, n-1, target) ☛  linerSearch(data, 5, 43)

▪︎ 두 번째 탐색

▫︎ (2번 라인) n = 5이므로 if(n < 0) 조건 불일치

▫︎ (5번 라인) else if(data[5] == target) 결과 값이 (100 != 43)이므로 조건 불일치

                   ☛ { 20, 15, 43, 66, 54, 100, 97 } != { 43 }

▫︎ (9번 라인) 재귀 함수 실행 : linerSearch(data, n-1, target) ☛  linerSearch(data, 4, 43)

▪︎ 세 번째 탐색

▫︎ (2번 라인) n = 4이므로 if(n < 0) 조건 불일치

▫︎ (5번 라인) else if(data[4] == target) 결과 값이 ( 54 != 43)이므로 조건 불일치

                   ☛ { 20, 15, 43, 66, 54, 100, 97 } != { 43 }

▫︎ (9번 라인) 재귀 함수 실행 : linerSearch(data, n-1, target) ☛  linerSearch(data, 3, 43)

▪︎ 네 번째 탐색

▫︎ (2번 라인) n = 3이므로 if(n < 0) 조건 불일치

▫︎ (5번 라인) else if(data[3] == target) 결과 값이 (66 != 43)이므로 조건 불일치

                   ☛ { 20, 15, 43, 66, 54, 100, 97 } != { 43 }

▫︎ (9번 라인) 재귀 함수 실행 : linerSearch(data, n-1, target) ☛  linerSearch(data, 2, 43)

▪︎ 다섯 번째 탐색

▫︎ (2번 라인) n = 2이므로 if(n < 0) 조건 일치

▫︎ (5번 라인) else if(data[] == target) 결과 값이 (43 != 43)이므로 조건 일치

                   ☛ { 20, 15, 43, 66, 54, 100, 97 } == { 43 }

▫︎ (6번 라인) n의 값 2를 반환 후 종료

✐ 코드 결과

다섯 번째 탐색까지 끝내고 출력되는 결과는 2이다.

재귀 함수를 이용해서 배열의 마지막 인덱스부터 1씩 줄여가면서 순차적으로 탐색하는 방법이다.

(배열에서 찾은 데이터의 위치를 반환하는 메서드)

✔︎ 오타, 틀린 개념이 있을 경우 댓글 달아주세요~!

(확인 후 수정하도록 하겠습니다~^^)

✔︎ 추가할 개념이 있다면 댓글 부탁드립니다~!

(지식을 공유해주세요~^^)