[알고리즘 독학] 검색 알고리즘 개념(1)

검색기법 3가지

- 배열검색
- 선형 리스트 검색
- 이진검색트리 검색

 

배열 검색

- 선형검색 : 늘어놓은 데이터를 검색
- 이진검색 : 일정한 규칙으로 늘어놓은 데이터를 검색
- 해시법 : 추가, 삭제가 자주 일어나는 데이터를 검색
  (체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법)
  (오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시 하는 방법)

 

 

선형 검색

요소가 직선 모양으로 늘어선 배열에서의 검색

- 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색

 

배열 검색의 종료 조건

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우

2. 검색할 값과 같은 요소를 발견한 경우

 

 

package search;

import java.util.Scanner;

public class Ex01 {

	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 stdIn = new Scanner(System.in);
		
		System.out.print("요소수 : ");
		int num = stdIn.nextInt();
		int[] x = new int[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 idx = seqSearch(x, num, ky);
		
		if(idx == -1) 
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");

		
	}

}

해당 메서드는 배열의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색하고 검색한 요소의 인덱스를 반환합니다.

또한 값이 key인 요소가 여러 개 존재할 경우 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 됩니다.

값이 key인 요소가 존재하지 않으면 -1을 반환합니다.

 

보초법

- 종료 조건을 검사하는 비용을 반으로 줄이는 방법

- 검색하기 전 요솟수에 1을 더하여 맨 끝 요소에 검색하고자 하는 키 값을 저장합니다.

 

package search;

import java.util.Scanner;

public class Ex02 {
	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 stdIn = new Scanner(System.in);
		
		System.out.print("요소수 : ");
		int num = stdIn.nextInt();
		int[] x = new int[num+1];             	//요소수 num + 1추가
		
		for(int i = 0; i < num; i++) {
			System.out.print("x["+i+"] : ");
			x[i] = stdIn.nextInt();
		}
		
		System.out.print("검색할 값 : ");
		int ky = stdIn.nextInt();
		
		int idx = seqSearch(x, num, ky);
		
		if(idx == -1) 
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");

		
	}


}