[ALGORITHM] 알고리즘 선형 검색

선형 검색

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데,

이것이 선형 검색이다.

 

public class SeqSearch {
	//요솟수가 n인 배열 a에서 key와 같은 요소를 선형 검색합니다.
	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을 반환)
		
	//while문		
	/*	int i = 0;
		while(true) {
			if(i == n)
				return -1;	//검색 실패(-1을 반환)
			if(a[i] == key)
				return i;	//검색 성공(인덱스를 반환)
			i++;
		}   */
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.print("요솟수 : ");
		int num = sc.nextInt();
		int[] x = new int[num];	//요솟수가 num인 배열
		
		for(int i=0; i<num; i++) {
			System.out.print("x[" + i + "] :");
			x[i] = sc.nextInt();
		}
		
		System.out.print("검색할 값 : ");//키 값을 입력
		int ky = sc.nextInt();
		
		int idx = seqSearch(x, num, ky);	//배열 x에서 키 값이 ky인 요소를 검색
		
		if(idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"는 x[" + idx + "] 에 있습니다.");
	}
}

 

 

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

1. i == n 이 성립(검색 실패이므로 -1을 반환)
2. a[i] == key가 성립(검색 성공이므로 i를 반환)

 

---

실행 결과

실행 결과