선형 검색(linear search)

• 선형 검색(linear search) 또는 순차 검색(sequential search)
• 배열에서 원하는 값을 가진 요소를 찾을 때까지 맨 앞에서부터 순서대로 요소를 검색하는 알고리즘

//선형 검색
public class SeqSearchFor {
    
    //길이가 n인 배열 a에서 key와 같은 요소를 선형 검색하여 그 요소의 인덱스를 반환한다
    private static int seqSearch(int[] a, int n, int key) {
        
            for (int i = 0; i < n; i++) {
                if (a[i] == key)
                    return i;
            }
            return -1;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        System.out.print("길이 : ");
        int num = scanner.nextInt();
        int[] x = new int[num];
 
        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "]：");
            x[i] = scanner.nextInt();
        }
 
        System.out.print("찾는 값 : ");
        int ky = scanner.nextInt();
 
        int idx = seqSearch(x, num, ky);
 
        if (idx == -1)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println("그 값은 x[" + idx + "]에 있습니다.");
    }
}

• 만약 while문으로 구현하면 배열 검색의 종료 조건이 2개가 된다.
  • [조건 1] : 검색할 값을 찾지 못하고 배열의 끝을 지나간 경우
  • [조건 2] : 검색할 값과 같은 요소를 발견한 경우

1 2 3 4 5 6 7 8 9 10 11 12

private static int seqSearch(int[] a, int n, int key) {          int i = 0;          while (true) {         if (i == n)             return -1;         if (a[i] == key)             return i;         i++;     } } Colored by Color Scripter

cs

• 종료 조건을 검사하는 비용을 반으로 줄이는 방법인 보초법(sentinel method)를 적용하면 원하는 값을 찾지 못했을 때를 판단하는 종료 [조건 1]이 없어도 된다.
  • 배열의 맨 끝에 찾고자 하는 값을 저장하는 데 이 값을 보초(sentinel)라고 한다.

//선형 검색(보초법)
public class SeqSearchSen {
 
    private static int seqSearchSen(int[] a, int n, int key) {
        int i = 0;
        a[n] = key; //보초를 추가
        
        while (true) {
            if (a[i] == key)
                break;
            i++;
        }
        
        return i == n ? -1 : i;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        System.out.print("길이：");
        int num = scanner.nextInt();
        int[] x = new int[num + 1]; //보초를 넣을 길이만큼
 
        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "]：");
            x[i] = scanner.nextInt();
        }
 
        System.out.print("검색할 값：");
        int ky = scanner.nextInt();
 
        int idx = seqSearchSen(x, num, ky);
 
        if (idx == -1)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println(ky+"은(는) x[" + idx + "]에 있습니다.");
    }
}

 

• while문에서 배열에 맨 끝에 도달했는지 판단하는 것과 현재 요소와 찾고자 하는 값이 같은지 판단하는 것의 평균 실행 횟수는 n / 2 이다. n에 비례하는 횟수만큼 실행하는 경우의 복잡도는 O(n)이다.
  • 컴퓨터에게 n / 2 과 n의 차이는 크지 않다. n / 2번 실행했을 때 복잡도를 O(n/2)가 아닌 O(n)으로 표현하는 이유는 n의 값이 무한히 커진다고 가정해도 그 값의 차이가 무의미하기 때문이다. 예를 들어 100번 실행하는 경우에도 O(100)이 아닌 O(1)로 표기한다. 컴퓨터가 100번 계산하는 시간과 1번만 계산하는 시간의 차이는 사람이 느낄 수 없을 정도로 굉장히 작기 때문이다.
• 2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 가장 높은 복잡도를 선택한다.