검색

선형검색이란 요소가 직선모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하는 방법을 말합니다.

package Chap03;
import java.util.*;

public class SeqSearch {
    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++;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.printf("요솟수: ");
        int num = sc.nextInt();
        int[] x = new int[num];

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

        System.out.printf("검색할 값: ");
        int ky = sc.nextInt();

        int idx = seqSearch(x, num, ky);

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

 

기본적인 사용방법입니다. 검색 횟수는 평균적으로 n/2입니다.

 

이진 검색은 정렬이 되어있어만 사용 가능한 검색 방법 입니다. up&down게임의 방식을 사용한다 보면 됩니다. 중간값을 기준으로 크고 작은지를 판단하여 데이터를 찾아냅니다. 평균적인 검색횟수는 logn 입니다.

 

그 예시

package Chap03;
import java.util.*;

public class BinSearch {
    static int binsearch(int[] a, int n, int key){
        int pl = 0;
        int pr = n-1;

        do{
            int pc = (pl+pr)/2;
            if(a[pc] == key)
                return pc;
            else if(a[pc] < key)
                pl = pc+1;      //검색범위를 뒤쪽 절반으로 좁힘
            else
                pr = pc-1;      //검색범위를 앞쪽 절반으로 좁힘
        }while(pl<=pr);

        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.printf("요솟수: ");
        int num = sc.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력하세요.");

        System.out.printf("x[0]: ");
        x[0] = sc.nextInt();

        for(int i=1; i<num; i++){
            do{
                System.out.printf("x["+i+"]: ");
                x[i] = sc.nextInt();
            }while(x[i] < x[i-1]);      //바로 앞의 요소보다 작으면 다시 입력
        }

        System.out.printf("검색할 값:");
        int ky = sc.nextInt();

        int idx = binsearch(x, num, ky);

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

 

시간복잡도는 O(n)입니다.