선형 탐색 Linear Search + 보초법 + Java 구현 코드

선형 탐색 (Linear Search)

개요

배열이나 리스트와 같은 데이터 구조에서 특정 값을 찾기 위해 각 요소를 순차적으로 비교하는 간단한 탐색 알고리즘.

(어레이 안의 모든 요소를 탐색)

 

선형 탐색의 개념

배열의 첫번째 요소부터 시작해서 마지막까지 순차적으로 각 요소를 확인함.

찾고자 하는 값과 일치하는 요소를 발견하면 해당 인덱스를 반환.

만약 배열의 모든 요소를 확인했음에도 불구하고 값을 찾지 못하면 -1을 반환.

 

시간 복잡도

최악의 경우 : O(n) - 배열의 모든 요소를 탐색해야 할 수도 있음.

최선의 경우 : O(1) - 첫 번째 요소가 찾고자 하는 값일 경우.

평균의 경우 : O(n) - 찾고자 하는 값이 배열의 중간에 있을 경우.

---

기본 구현 코드

// 선형 탐색 (기본)
static int seqSearch(int[] arr, int target) {
    int idx = 0;    // 반환할 인덱스 변수 (0부터 탐색 시작)

    // 반복문 1회 -> 2개의 조건문 연산
    while (true) {
        // 종료조건: idx가 arr의 끝(=arr.length-1)을 초과하면 
        if ( idx == arr.length ) return -1;
        // 반환조건: arr의 값이 target과 일치하면 idx를 반환
        if ( arr[idx] == target ) return idx;
        idx++;
    }
}

 

보초법 (개선된 버전)

~ 보초법을 사용했을 때의 이점 ~

 

1. 루프 종료 조건 단순화

• 보초법을 사용하면, 마지막 요소에 검색할 값을 미리 설정하여 루프 종료 조건을 단순화할 수 있습니다.
  일반적인 선형 탐색에서는 배열의 범위를 초과하지 않도록 인덱스를 체크해야 하지만, 보초법을 사용하면 이러한 체크가 필요 없어집니다.
• 예를 들어, while (true) 루프를 사용하여 target을 찾을 때까지 계속 탐색할 수 있습니다.

2. 성능 향상

• 보초법을 사용하면, 루프 내에서 인덱스의 유효성을 체크하는 조건문이 필요 없으므로, 조건문에 대한 오버헤드가 줄어듭니다. 이는 특히 반복 횟수가 많을 때 성능 향상으로 이어질 수 있습니다.

3. 코드 가독성 향상

• 보초법은 코드의 가독성을 높여 줍니다. 루프가 종료되는 조건을 명시적으로 체크할 필요가 없어지므로, 코드가 더 간결해지고 이해하기 쉬워집니다.

4. 모든 요소 탐색 보장

• 보초법을 사용하면, 배열의 마지막 요소까지 탐색하게 되므로, target이 배열의 마지막에 있을 때도 이를 찾을 수 있습니다. 일반적인 선형 탐색에서는 루프가 종료되기 전에 target을 찾지 못할 수 있지만, 보초법은 이 문제를 해결합니다.

5. 특별한 경우 처리 용이

• 보초법을 사용하면, 배열의 모든 요소를 탐색한 후에도 target이 존재하지 않을 경우, return -1과 같은 처리를 간단하게 할 수 있습니다. 이로 인해 예외적인 상황을 다루기 쉬워집니다.

// 선형 탐색 (보초법)
static int seqSearchSentinel(int[] arr, int target) {
    // 반환조건: arr의 마지막 요소가 target이라면, 바로 lastIdx를 반환
    int lastIdx = arr.length - 1;
    if (arr[lastIdx] == target) return lastIdx;

    // 위의 조건에 맞지 않는다면, 이하의 과정을 진행
    // 배열의 마지막 인덱스 위치에 target을 넣음 (보초)
    arr[lastIdx] = target;

    // 종료 조건 1번(인덱스 범위 검사)이 필요 없어지고, 탐색할 데이터의 크기가 1 줄어듦
    // 즉, 반복문 1회 -> 조건문 비교 연산 1회
    int idx = 0;
    while (true) {
        if (arr[idx] == target) {
            // 반환조건: 전체 탐색에서 딱 1번만 실행됨
            return (idx < lastIdx) ? idx : -1;
        }
        idx++;
    }
}

 

테스트 코드

// Test Run
public static void main(String[] args) {
    int index = seqSearch(new int[]{1,6,12,4,76,23,411}, 4);
    System.out.println(index);
}