알고리즘 3.1 검색 (선형 검색)

1. 선형검색(순차검색)

요소가 직선 모양으로 늘어선 배열에서 검색을 원하는 킷값을 갖는 요소를 만날때까지무작위로 늘어서 있는 데이터 모임에서 검색을 수행

검색 성공 : 검색할 값과 같은 요소를 발견한 경우
검색 실패 : 검색할 값을 발견하지 못하고 배열의 끝을 지나가는 경우

장점 : 정렬이 안 되어있어도 검색 가능함
단점 : 순차적으로 검색하기 때문에 데이터가 많아지면 검색 시간이 오래 걸림

선형검색 예제 )

n개의 요소를 가진 배열 a에서 key값을 검색하는 코드

public class LinearSearch {
	public  int seqSearch(int n, int[]a, int key) {
    	// 배열의 a의 처음부터 끝까지 n개인 요소를 대상으로 값이 key인 요소를 검색
		int i=0;
		while(true) {
			if (i == n) 
				return -1;	// 검색 실패
			else if(a[i] == key) return idx;
			i++; 			// 검색 성공, 검색한 요소의 인덱스 반환
		}
		
	}

	public static void main(String[] args) {
		
		LinearSearch ls = new LinearSearch(); // 객체생성
		
		
		Scanner stdin = new Scanner(System.in);
		System.out.print("요소수 : ");
		int n = stdin.nextInt(); // 요소의 개수
		int a[] = new int[n];
				
		for(int i=0; i<n; i++) {
			System.out.println("a[" + i + "] : ");
			a[i] = stdin.nextInt();
		}
		
		System.out.println("검색할 값 : ");
		int key = stdin.nextInt();
		
		int idx = ls.seqSearch( n, a, key ); // 배열 a에서 값이 key인 요소 검색
		if (idx == -1) 
			System.out.println("검색한 값의 요소가 없습니다.");
		else 
			System.out.println("검색한 값은 " + idx + "번에 있습니다.");
		if (stdin != null) stdin.close();
	}

}

2. 보초법으로 선형검색

보초법 :
특정한 값인 보초값을 사용하여 종료 조건중 검색 실패 조건을 제거하여 판단 횟수를 줄이는 방법

배열의 맨 끝 요소에 검색하고자 하는 키값을 보초로 저장

종료조건 1 : 건색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
종료조건 2 : 검색할 값과 같은 요소를 발견한 경우

원하는 값이 원래 데이터에 존재하지 않아도 보초인 방가지 검색하면 종료 조건 2가 성립
=> 종료조건 1이 없어도 됨
=> 종료조건 판단 횟수 줄임

보초법으로 예제 풀이)

public class LinearSearch {
	public int seqSearch(int n, int a[], int key) {
		// 보초법 사용 : 맨 끝 방에 검색할 값 넣음 => 방이 하나 더 있어야 함
		a[n] = key; // 맨 끝 방에 보초값 넣어줌 (배열은 0부터기때문에 n이 가장 마지막 방임)
		int i=0;
		while (true) {
			if(a[i] == key)
				break; // 검색성공
			i++;	
		}
		return i == n ? -1 : i;	//if문 대신 조건 사용
	}
    
// 종료조건 중 하나인 (i == n)이 필요하지 않기 때문에
// 종료조건 (a[i] == key) 만 판단하면 됨

	public static void main(String[] args) {
		LinearSearch ls = new LinearSearch(); // 객체생성
		
		
		Scanner stdin = new Scanner(System.in);
		System.out.println("요소수 : ");
		int n = stdin.nextInt(); // 요소의 개수
		int a[] = new int[n+1]; // 보초가 저장될 방 하나를 더해주어야 함.
				
		for(int i=0; i<n; i++) {
			System.out.println("a[" + i + "] : ");
			a[i] = stdin.nextInt();
		}
		
		System.out.println("검색할 값 : ");
		int key = stdin.nextInt();
		
		int idx = ls.seqSearch( n, a, key ); 
		if (idx == -1) 
			System.out.println("검색한 값의 요소가 없습니다.");
		else 
			System.out.println("검색한 값은 " + idx + "번에 있습니다.");
		if (stdin != null) stdin.close();

	}

}