선형 탐색(Linear Search)

🔍 선형 탐색(Linear Search) 알고리즘이란?

**선형 탐색(또는 순차 탐색)**은 가장 기본적이고 간단한 탐색 알고리즘입니다. 데이터를 처음부터 끝까지 하나씩 차례대로 확인하면서 **찾고자 하는 값(키 값)**을 찾는 방식입니다.

 

선형 탐색(Linear Search) 알고리즘

---

✅ 작동 방식

1. 배열이나 리스트의 첫 번째 요소부터 시작합니다.
2. 각 요소를 하나씩 검사하여, 찾고자 하는 값인지 확인합니다.
3. 찾으면 즉시 반환하고, 끝까지 없으면 “찾을 수 없음”을 반환합니다.

---

🔄 동작 예시

배열: [10, 25, 37, 40, 52]
찾고자 하는 값: 37

1. 10 → 아니고
2. 25 → 아니고
3. 37 → 찾음! → 인덱스 2 반환

---

📊 시간 복잡도

상황시간 복잡도

최선 (첫 번째 원소가 정답)	O(1)
평균	O(n)
최악 (마지막 원소 또는 없음)	O(n)

 

※ n은 배열의 크기입니다.

---

✅ 장점과 단점

✅ 장점

• 구현이 매우 간단함
• 정렬이 되어 있지 않아도 사용 가능
• 소규모 데이터에서는 충분히 빠름

❌ 단점

• 검색 속도가 느림 (특히 대용량일 경우)
• 비효율적 (중복된 비교가 많음)

---

🧪 Java 예제 코드

public class LinearSearchExample {

    // 선형 탐색 메서드
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 찾은 경우 인덱스 반환
            }
        }
        return -1; // 찾지 못한 경우
    }

    public static void main(String[] args) {
        int[] numbers = {10, 25, 37, 40, 52};
        int target = 37;

        int result = linearSearch(numbers, target);

        if (result != -1) {
            System.out.println("값 " + target + "은 인덱스 " + result + "에 있습니다.");
        } else {
            System.out.println("값 " + target + "을 찾을 수 없습니다.");
        }
    }
}

🖥️ 출력 결과

 

값 37은 인덱스 2에 있습니다.

---

📌 정리

항목설명

알고리즘 이름	선형 탐색 (Linear Search)
사용 조건	정렬 여부 상관없음
장점	단순하고 직관적, 소규모에 적합
단점	대규모 데이터에서 느림
시간 복잡도	O(n)

 

 

---

✅ 언제 사용할까?

• 데이터가 정렬되지 않았을 때
• 데이터 크기가 작을 때
• 간단한 코드가 필요한 상황