[알고리즘] 선형 검색(LinearSearch, SequenceSearch)

 

선형검색(LinearSearch, SequenceSearch)

: 원하는 키값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하는 방법

배열의 0부터 n까지 하나씩 찾음

 

 

package al02_search;

import java.util.Scanner;

//선형검색(LinearSearch, SequenceSearch)
//순차적으로 검색

public class SequenceSearch {
	
	//for문 이용해 검색
	//key값이 있는 위치를 구해 index 반환
	//								배열    데이터 수, key값
	static int linearSearch1(int[] data, int n, int key) {
		// 배열에서 key값을 검색해 index리턴
		// 검색된 index가 없으면 -1 리턴
		for(int i=0; i<n; i++) {
			if(data[i]==key) {
				return i; 	// 메소드 ㅈ종료
			}
		}
		return -1;
	}
	// while문을 이용한 데이터 위치 검색
	static int linearSearch2(int[] data, int n, int key) {
		int i=0;
		while(true) {
			if(i==n) {	// i index가 존재하는가
				return -1;
			}
			if(data[i]==key) {	// 검색할 데이터를 찾은 경우
				return i;
			}
			// 다음 index의 값을 확인하기 위해 index 1 증가
			i++;	// ++i, i+=1, i=i+1 모두 가능
		}
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		//	데이터 갯수 입력 : 배열 생성
		System.out.print("데이터 수->");
		int n = s.nextInt();

		// 배열 생성
		int data[] = new int[n];
		
		// 데이터 입력
		for(int i=0; i<n; i++) {
			System.out.print("data["+i+"]=");
			data[i] = s.nextInt();
		}

		//찾을 숫자를 입력받음
		System.out.print("검색할 데이터->");
		int key = s.nextInt();
		
		//for문을 이용한 선형검색 호출
		int idx = linearSearch1(data,n, key);
		
		if(idx>=0) {//검색한 데이터 있을 때
			System.out.println(key+"는 data["+idx+"]위치에 있습니다.");
		}else {
			System.out.println(key+"는 존재하지 않는 데이터입니다.");
		}
		
		// while문을 이용한 선형검색 호출
		int idx2 = linearSearch2(data, n, key);
		
		if(idx2>=0) {//검색한 데이터 있을 때
			System.out.println(key+"는 data["+idx+"]위치에 있습니다.");
		}else {
			System.out.println(key+"는 존재하지 않는 데이터입니다.");
		}
		s.close();
		
	}

}