Algorithm | 선형 탐색(순차 검색, Linear search)

선형 탐색 알고리즘(순차검색, Linear search algorithm)

찾고자 하는 값을 리스트의 맨 앞에서부터 끝까지 차례대로 찾아 나가는 알고리즘이다.

  • 장점: 검색 방법 중 가장 단순하여 구현이 쉽고, 정렬되지 않은 리스트에서도 사용할 수 있다.
  • 단점: 검색할 리스트의 길이가 길면 비효율적이다.
package com.devkuma.algorithum.programming.search.linear;

public class LinearSearch {

    void search(int[] nums, int target) {
        int index = -1;
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                index = i + 1;
                break;
            }
        }
        if (index > 0) {
            System.out.println(target + "은 " + index + "번째 있습니다.");
        } else {
            System.out.println(target + "은 없습니다.");
        }
    }

    public static void main(String[] args) {
        LinearSearch search = new LinearSearch();
        search.search(new int[]{1, 5, 3, 2, 8, 9}, 8);
        search.search(new int[]{1, 5, 3, 2, 8, 9}, 4);
    }
}

실행 결과:

8은 5번째 있습니다.
4은 없습니다.

선형 탐색 알고리즘으로 최소값 구하기

아래 코드는 모든 요소에 대해서 minValue보다 작은 값이 발견될 때마다 minValue를 갱신해 가면 최소값을 구한다. (최대값도 동일한 알고리즘이다)

package com.devkuma.algorithum.programming.search.linear;

public class MinLinearSearch {

    void searchMinimum(int[] nums) {
        int minValue = Integer.MAX_VALUE; // 최대값
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] < minValue) {
                minValue = nums[i];
            }
        }
        System.out.println("최소값은 " + minValue + "입니다.");
    }

    public static void main(String[] args) {
        MinLinearSearch search = new MinLinearSearch();
        search.searchMinimum(new int[]{1, 5, 3, 2, 8, 9});
        search.searchMinimum(new int[]{2, 7, 8, 6, 5, 4});
    }
}

실행 결과:

최소값은 1입니다.
최소값은 2입니다.

선형 탐색 알고리즘으로 최소값 구하기

이제 선형 탐색 알고리즘을 이용해서 문제를 풀어보자.

문제
N개의 정수 a(0), a(1), ..., a(N-1)b(0), b(1), ..., b(N-1)가 있다고 했을 때, 이 2개의 수열로부터 하나씩 수 a(i), b(j) [i = 0, 1, ..., N-1, j = 0, 1, ..., N-1]를 구해서 그 합이 정수 R 이상의 범위에서의 최소값을 구하라.

해결 방법

package com.devkuma.algorithum.programming.linearsearch;

public class LinearSearchQuiz1 {

    void minSum(int[] aNums, int[] bNums, int r) {
        int minSum = Integer.MAX_VALUE; // 최대값
        for(int i = 0; i < aNums.length; i++) {
            for(int j = 0; j < bNums.length; j++) {
                int sum = aNums[i] + bNums[j];
                if (sum >= r && minSum > sum) {
                    minSum = sum;
                }
            }
        }
        System.out.println("최소값은 " + minSum + "입니다.");
    }

    public static void main(String[] args) {
        LinearSearchQuiz1 search = new LinearSearchQuiz1();

        int[] aNums =   new int[]{9, 5, 3, 7, 8, 9};
        int[] bNums =   new int[]{3, 9, 5, 8, 3, 5};
        int r = 7;
        search.minSum(aNums, bNums, 7);
    }
}

실행 결과:

최소값은 8입니다.

위 예제의 복잡도는 O(N^2)이 된다.