선형 탐색 알고리즘은 리스트나 배열에서 특정 값을 찾는 데 사용되는 간단한 알고리즘입니다. 이 알고리즘은 리스트의 처음부터 끝까지 차례대로 검색하며 원하는 값을 찾으면 탐색을 중지합니다.

알고리즘 동작 원리

1. 리스트의 첫 번째 요소부터 시작합니다.
2. 현재 요소와 찾고자 하는 값이 일치하는지 확인합니다.
3. 일치하는 경우, 탐색을 종료하고 해당 요소의 인덱스를 반환합니다.
4. 일치하지 않는 경우, 다음 요소로 이동하여 2번 단계부터 반복합니다.
5. 모든 요소를 확인했는데도 일치하는 값이 없는 경우, 탐색을 종료하고 -1을 반환합니다.

코드 예시

public class LinearSearch {
    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[] arr = {3, 7, 1, 9, 5};
        int target = 9;
        int result = linearSearch(arr, target);
        if (result != -1) {
            System.out.println("찾고자 하는 값의 인덱스: " + result);
        } else {
            System.out.println("찾고자 하는 값이 배열에 존재하지 않습니다.");
        }
    }
}

위 예시 코드는 linearSearch라는 이름의 정적 메소드를 가진 LinearSearch 클래스를 정의하고 있습니다. linearSearch 메소드는 주어진 배열과 찾고자 하는 값(target)을 인자로 받아 선형 탐색을 수행하고 결과로 찾고자 하는 값의 인덱스를 반환합니다.

main 메소드에서는 선형 탐색을 수행할 배열과 찾고자 하는 값을 지정하고, linearSearch 메소드를 호출하여 결과를 출력합니다.

시간 복잡도

선형 탐색 알고리즘의 시간 복잡도는 O(n)입니다. 리스트의 모든 요소를 순차적으로 검색하기 때문에 최악의 경우 n번의 반복이 필요합니다.