[ 자바 알고리즘/자료구조] - 자바 선형 검색(탐색) & 보초법

선형 검색이란?

- 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 앞에서부터 끝까지 돌면서 찾는 검색

 

배열 인덱스	0	1	2	3	4
배열 요소	2	7	5	1	9

배열의 0번째 인덱스부터 -> 4번째 인덱스 까지 검색을 하는 것이다.

 

선형 검색의 종료 조건

1) 검색에 실패하고 배열의 끝을 지난 경우

   - n+1회

2) 검색에 성공했을 때

   - n회

-> 평균은 n/2회

 

코드

public class 선형검색 {
	static int seqSearch(int[] a, int n, int key) {
		int i=0;
		
		while(true) {
			if(i==n) 
				return -1;
			if(a[i] == key)
				return i;
			i++;
		}
        
//      - for문 구현 -
//       int result = -1;
//		for(int i=0; i<n; i++) {
//			if(a[i] == key) {
//				result = i;
//			}
//		}
//		return result;

	}
	public static void main(String[] args) {
		int[] arr = {5,3,8,2,1,9,4,6};
		Scanner s= new Scanner(System.in);
		int key = s.nextInt();
		int idx = seqSearch(arr, arr.length, key);
		System.out.println(Arrays.toString(arr));
		if(idx >= 0) {
			System.out.println(idx + "번째 위치함");
		}else {
			System.out.println("해당 요소를 찾지 못함");
		}
	}
}

- 선형 탐색을 실행할 메서드 seqSearch를 생성하며 인자로는 탐색할 배열, 배열의 길이, 찾는 값을 받는다.

- 배열의 시작 인덱스는 0이기 때문에 카운터(i)값을 0으로 초기화 후 while문(for문)을 통해 루프를 돈다.

- 이때, i가 배열의 길이와 같으면 -1을 반환

   ( 배열을 지나치면 검색 종료라고 했는데 왜 i == n 일까? -> 배열의 위에 arr은 배열의 길이가 8이다.

    하지만 인덱스는 0부터 7까지다. i가 8이되면 배열의 인덱스를 지나친 것이다. )

- 만약 원하는 값을 찾았다면 i값을 반환한다.

 

-> 선형 검색은 구현은 단순하지만 종료 조건을 검사하는 비용이 생각보다 무시하지 못한다.

-> 그렇다면 이를 줄일 수 있는 방법은?

-> " 보초법 "

-> 보초법을 통해 비용을 50% 줄일 수 있다.

 

보초법

- 검색에 실패했을 경우를 대비해 맨 끝 요소에 원하는 키 값을 준비한다.

배열 인덱스	0	1	2	보초인덱스
배열 요소	5	2	3	찾을 요소

public class 선형검색보초법 {
	static int seqSearch(int[] a, int n, int key) {
		int i=0;
		
		a[n] = key;
		
		while(true) {
			if(a[i] == key) {
				break;
			}
			i++;
		}
		return i == n ? -1 : i;
	}
	public static void main(String[] args) {
		int[] arr = {5,3,8,2,1,9,4,6};
		Scanner s= new Scanner(System.in);
		int key = s.nextInt();
		
		int[] tmp = new int[arr.length + 1];  //보초
		for(int i=0; i<arr.length; i++) {
			tmp[i] = arr[i];
		}
		
		int idx = seqSearch(tmp, arr.length, key);
		System.out.println(Arrays.toString(arr));
		if(idx >= 0) {
			System.out.println(idx + "번째 위치함");
		}else {
			System.out.println("해당 요소를 찾지 못함");
		}
	}
}

- 우선 tmp라는 보초배열에 원래 배열 arr 길이보다 + 1상태로 만들어 준다.

- 배열을 arr길이만큼 복사하면 마지막 인덱스는 타입에 맞게 초기화 되어있을 것이다.

- seqSearch를 호출할때 조심하자. -> 배열은 보초배열(tmp)을 넘기지만 길이(n)은 원래배열의 길이를 넘겼다.

- seqSearch 메서드를 보면 조금 달라졌는데 앞선 i == n 일떼 -1 반환하는 코드가 사라졌다.

- 어짜피 tmp배열에 마지막 요소에 찾고자 하는 값을 넣어뒀기 때문에 불필요한 연산을 줄인것이다.

- 마지막 return을 보면 i가 n의 길이와 같으면 -1 즉, 못찾았다는 뜻, i면 인덱스를 반환한다.