Chapter 03-2. 검색 알고리즘_선형 검색

선형 검색(linear search) 또는 순차 검색(sequential search)

요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색함

배열의 요솟수가 n개일 때 종료조건(검색 실패 혹은 성공)을 판단하는 횟수는 평균 n/2회

int i = 0;

while(true) {
	if(i == n)
		return -1; // 검색 실패(-1 반환)
	if(a[i] == key)
		return i; // 검색 성공(인덱스 반환)
	i++;
}

 

선형 검색

package ch03_2;

import java.util.Scanner;

// 선형 검색
public class Ex01_seqSearch {
    // 요솟수가 n인 배열 a에서 key와 값이 같은 요소를 선형 검색
    static int seqSearch(int[] a, int n, int key) {
        int i = 0;

        while(true) {
            if(i == n)
                return -1; // 검색 실패(-1 반환)
            if(a[i] == key)
                return i; // 검색 성공(인덱스 반환)
            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]; // 요솟수가 num인 배열

        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        System.out.print("검색할 값: "); // 키 값
        int key = scanner.nextInt();

        int index = seqSearch(x, num, key);

        if(index == -1) {
            System.out.println("그 값의 요소가 없습니다.");
        } else {
            System.out.println("그 값은 x[" + index + "]에 있습니다.");
        }
    }
}

/*
요솟수: 5
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 2
검색할 값: 7
그 값은 x[3]에 있습니다.
 */

 

무한 루프 구현

while(true) {}
for(; true ;) {} // 제어식 생략
do {} while(true) // 끝까지 읽어야 무한루프 알 수 있기에 권장x

 

선형 검색 for문

package ch03_2;

import java.util.Scanner;

// 선형 검색 for문
public class Ex02_seqSearchFor {
    // 요솟수가 n인 배열 a에서 key와 값이 같은 요소를 선형 검색
    static int seqSearch(int[] a, int n, int key) {
        for (int i = 0; i < n; i++) {
            if(a[i] == key)
                return i; // 검색 성공(인덱스 반환)
        }
        return -1; // 검색 실패(-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]; // 요솟수가 num인 배열

        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        System.out.print("검색할 값: "); // 키 값
        int key = scanner.nextInt();

        int index = seqSearch(x, num, key);

        if(index == -1) {
            System.out.println("그 값의 요소가 없습니다.");
        } else {
            System.out.println("그 값은 x[" + index + "]에 있습니다.");
        }
    }
}

/*
요솟수: 3
x[0]: 1
x[1]: 2
x[2]: 3
검색할 값: 5
그 값의 요소가 없습니다.
 */

 

보초법(sentinel method)

준비해 놓은 배열 a[0]~a[6] + a[7] 은 검색하고자 하는 키값을 저장하는 보초(sentinel)

위와 같이 보초에 저장해 두면 종료 조건 중 하나인 검색 실패(검색 값을 발견하지 못하고 배열의 끝을 지나간 경우)를 고려하지 않아도 되기에 종료 조건 검사 비용이 반으로 줄어듦

 

선형 검색(보초법)

package ch03_2;

import java.util.Scanner;

// 선형 검색(보초법)
public class Ex03_seqSearchSen {
    // 요솟수가 n인 배열 a에서 key와 값이 같은 요소를 보초법으로 선형 검색
    static int seqSearchSen(int[] a, int n, int key) {
        int i = 0;

        a[n] = key; // 보초를 추가

        while (true) {
            if(a[i] == key) // 검색 성공 - 보초법을 사용해 하나의 if문만 사용
                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]; // 요솟수가 num + 1 인 배열

        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        System.out.print("검색할 값: "); // 키값
        int key = scanner.nextInt();

        int index = seqSearchSen(x, num, key); // 배열 x에서 값이 key인 요소 검색

        if(index == -1) {
            System.out.println("그 값의 요소가 없습니다.");
        } else {
            System.out.println("그 값은 x[" + index + "]에 있습니다.");
        }
    }
}

/*
요솟수: 5
x[0]: 1
x[1]: 3
x[2]: 2
x[3]: 3
x[4]: 4
검색할 값: 3
그 값은 x[1]에 있습니다.
 */