선형검색(순차검색) linear search, sequential search

요소가 직선 모양으로 늘어선 배열에서 처음부터 끝까지 원하는 키 값을 앞에서부터 순서대로 요소를 검색하는 것.

검색의 종료 조건은 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우나 검색할 값과 같은 요소를 발견한 경우 두 경우이다. 전자는 검색 실패이고 후자는 검색 성공이다. 배열의 요솟수가 n 개일 때, 위 두 가지 결과를 판단하는 횟수는 평균 n/2회 이다.

(원하는 값이 배열에 존재하지 않는 경우 전자는 n+1회, 후자는 n회)

 

public class SeqSearch {

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