순차 검색 알고리즘 (Sequential Search)

- 순차 검색 == 선형 검색 알고리즘

순차 검색 알고리즘은 단어 그대로의 알고리즘 입니다. 리스트에서 맨 앞에서부터 끝까지 차례대로 찾고자 하는 값을 찾는 방법입니다.

 

검색 방법 중 가장 단순한 방법이자만 리스트의 길이가 길어질 수록 검색하는데 시간이 오래걸리고 비효율적인 방법입니다.

 

시간 복잡도는 O(n) 입니다.

 

※ 1차 for문을 O(n) 이라고 표현 합니다.

 

public class SequentialSearch {
	/**
	 * 순차 탐색
	 * 
	 * O(n) 의 시간 복잡도를 가진다.
	 * 
	 * for 문은 O(n) 의 시간 복잡도를 가진다.
	 * 
	 * @param intList 	검색 대상
	 * @param target	검색할 값
	 * @return			검색된 값 index
	 */
	static int searchIndex (int[] intList, int target) {
		int check = -1;
		for (int i=0; i<intList.length; i++) {
			if (intList[i] == target) {
				check = i;
			}
		}
		return check;
	}
	
	
	public static void main(String[] args) {
		int[] intList = {11, 22, 33, 44, 55, 66, 77, 88};
		
		Scanner sc = new Scanner(System.in);
		int a =  Integer.parseInt(sc.next());
		sc.close();
		int returnValue = searchIndex(intList, a);
		
		if (returnValue == -1) {
			System.out.println("찾는 값이 없습니다.");
		} else {
			System.out.println("찾는 값은 배열의 " + returnValue + "번째 index에 있습니다.");
		}
	}
}