[Java] 검색

Do it! 자료구조와 함께 배우는 알고리즘 입문 읽고 정리

 

3-1 검색 알고리즘

배열에서 검색하기

1. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행

2. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행

3. 해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색 수행

 - 체인 법: 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법

 - 오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

 

3-2 선형 검색

선형 검색

 

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) {
    	int[] x = {1, 2, 3, 4, 5};
 		int key = 4;
        int idx = seqSearch(x, x.length(), key);
        
        if (idx == -1) System.out.println("실패");
        else System.out.println(key+"는 [x" + idx + "]에 있다.");
    }
}

- 배열 처음부터 끝까지 n개의 요소를 대상으로 순차적으로 검색

 

보초법

선형 검색은 반복할 때마다 검색할 값을 발견하지 못하고 배열의 끝을 지나가거나 검색할 값과 같은 요소를 발견할 경우 두 가지 종료 조건이 있다. 매우 비효율적

이를 효율적으로 선형 검색보다 효율적인 보초법이 있다.

class SeqSearchSen {
	static int seqSearch(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 sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] x = int[num + 1];
        
        for (int i=0; i < num; i++) {
        	x[i] = sc.nextInt();
        }
 		int key = 4;
        int idx = seqSearchSen(x, num, key);
        
        if (idx == -1) System.out.println("실패");
        else System.out.println(key+"는 [x" + idx + "]에 있다.");
    }
}

 

3-3 이진 검색

이진검색

이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

class BinSearch {
	// 요소수가 n인 배열 a에서 key와 같은 요소를 이진 검색한다.
    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 (pc <= pr)
        
        return -1; // 검색 실패
    }
    
    public static void main(Stringp[] args) {
    	Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] x = new int[num];
        
        x[0] = sc.nextInt();
        
        for (int i=1; i < num; i++) {
        	do {
            	x[i] = sc.nextInt();
            } while (x[i] < x[i-1]); // 앞 요소보다 작으면 다시 입력
        }
        
        int key = sc.nextInt();
        
        int idx = binSearch(x, num, key);
        
        if (idx == -1) System.out.println("failed!");
        else System.out.println("There is" + key + " in x[" + idx + "]!);
    }

}

 

복잡도

알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다.

1. 시간 복잡도: 실행에 필요한 시간을 평가한 것

2. 공간 복잡도: 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

- 연습문제

Q3 요소수가 n인 배열 a에서 key와 일치하는 모든 요소의 인덱스를 배열 idx의 맨 앞부터 순서대로 저장

일치한 요소수를 반환하는 메소드 작성

ex) 요소수가 8인 배열 a의 요소가 {1, 9, 2, 9, 4, 6, 7, 9} 이고, key가 9면 배열 idx에 {1, 3, 7}을 저장하고 3을 반환한다.

// 배열 a의 앞쪽 n개 요소에서 key와 같은 모든 요소의 index를 배열idx의 머리부터 차례로 저장하여 같은 요솟수를 반환
static int searchIdx(int[] a, int n, int key, int[] idx) {
    int count = 0; // key와 같은 요솟수
    for (int i = 0; i < n; i++)
        if (a[i] == key)
            idx[count++] = i;
    return count;
}

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

    System.out.print("요솟수：");
    int num = stdIn.nextInt();
    int[] x = new int[num]; // 요솟수 num인 배열
    int[] y = new int[num]; // 요솟수 num인 배열

    for (int i = 0; i < num; i++) {
        System.out.print("x[" + i + "]：");
        x[i] = stdIn.nextInt();
    }
    System.out.print("찾는 값："); // 키 값을 입력 받음
    int ky = stdIn.nextInt();

    int count = searchIdx(x, num, ky, y);

    if (count == 0)
        System.out.println("그 값의 요소가 없습니다.");
    else
        for (int i = 0; i < count; i++)
            System.out.println("그 값은 " + "x[" + y[i] + "]에 있습니다.");
}

 

Arrays.binarySearch로 이진 검색

Java에서는 배열에서 이진 검색을 할 수 있는 메소드를 표준 라이브러리로 제공한다.

이진 검색을 직접 코딩할 필요 없이 가져다 사용하면 된다.