선형 검색(Linear Search)

선형 검색(Linear Search)은 가장 간단한 형태의 검색 알고리즘이다.

이 알고리즘은 주어진 데이터 집합에서 특정 값을 찾기 위해 처음부터 끝까지 순차적으로 검색하는 방식을 사용한다. 순차적으로 하나씩 확인하기 때문에 선형 검색이라는 이름이 붙었었다.

아래는 선형 검색의 단계이다.:

1. 배열의 첫 번째 요소부터 시작하여, 특정 값이 발견될 때까지 각 요소를 차례대로 확인한다.
2. 만약 해당 값이 발견되면, 그 위치(또는 인덱스)를 반환한다.
3. 만약 배열의 끝까지 검색하고도 해당 값이 없다면, 검색 실패를 의미하는 값을 반환한다. (예: -1)

선형 검색의 가장 큰 단점은 시간 복잡도가 O(n)이라는 점이다. 즉, 데이터의 양이 증가함에 따라 검색 시간도 비례하여 증가하게 된다. 따라서 큰 데이터 집합에서는 효율적이지 않을 수 있다. 하지만 데이터가 작거나, 데이터가 정렬되어 있지 않은 경우에는 간단하고 효율적으로 사용할 수 있는 알고리즘이다.

class LinearSearchExample {
    // 선형 검색 메소드
    static int linearSearch(int[] arr, int x) {
        int n = arr.length;
        for(int i = 0; i < n; i++) {
            if(arr[i] == x)
                return i; // 요소가 발견되면 해당 인덱스 반환
        }
        return -1; // 요소가 발견되지 않으면 -1 반환
    }

    public static void main(String args[]) {
        int[] arr = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
        int x = 110; // 찾고자 하는 값
        int index = linearSearch(arr, x);
        if(index == -1)
            System.out.println("Element is not present in the array");
        else
            System.out.println("Element found at position: " + index);
    }
}

linearSearch 메소드는 배열과 찾고자 하는 값을 인수로 받아서 배열의 각 요소를 처음부터 끝까지 순차적으로 비교한다. 만약 찾고자 하는 값이 배열의 요소와 일치하면 해당 요소의 인덱스를 반환한다. 만약 배열을 모두 탐색했음에도 찾고자 하는 값이 없으면 -1을 반환한다.