[알고리즘] 순차검색 + 보초법

검색 알고리즘

어떤 데이터 집합에서 원하는 값을 가진 요소를 찾아냄

검색 기법은 어떤 자료구조를 사용하는가, 어떤 검색알고리즘을 사용하는가에 따라 달라진다.
책에 나와있는 예시로는

1. 배열검색
2. 선형리스트 검색
3. 이진검색트리 검색

이렇게 3개가 나와있다.

이번 포스팅에서는 배열을 검색하는 방법들 중에서 순차검색(선형검색)과 보초법을 다룬다.

선형검색

선형검색 혹은 순차검색이라고도 불린다.
무작위로 늘어놓은 데이터들을 처음부터 하나씩 비교해가며 내가 원하는 값을 찾는 것이다.

//요소의 개수가 n개인 정수형 배열 a에서 key와 같은 요소를 순차검색
	static int seqSearch(int[]  a, int n, int key) {
		int i=0;
		/*
		 * 아래 무한루프에서 조건을 판단하는 부분은 총 3군데 이다. 
         	 * while(true)또한 조건을 판단하는 곳이다.
		 */
		while(true) {
			if(i==n) {
				return -1;
			}
			if(a[i]==key) {
				return i;
			}
			i++;
		}
	}

검색이 끝나는 조건은 2가지이다.

인덱스 i의 값을 1씩 증가시키며 배열의 값들을 key값과 비교를 하는데
1. 중간에 key와 값이 일치하는 배열의 요소를 찾았다 => 검색 성공!
2. 배열의 끝을 지났다. => 일치하는 값이없으므로 검색 실패!

위에선 while문을 사용하였지만 for문을 사용하면 훨씬 간단하다.

//위 메서드를 while이 아닌 for을 이용하여 작성 => 더 깔끔
	static int seqSearchFor(int[] a, int n, int key) {
		for(int i=0;i<n;i++) {
			if(a[i]==key) {
				return i;
			}
		}
		return -1;
	}

보초법

위에서 작성한 선형검색에서 종료조건판단을 하는 횟수를 절반으로 줄일 수 있는 일종의 선형검색 업그레이드방법이다.
종료조건중 배열의 끝을 지났나? 하고 판단하는 것을 안해도 된다.
배열의 끝에 찾으려는 key값을 저장하면 된다. 얘를 Sentinel, 보초라고 부른다.

//보초법을 이용해 선형검색 => 위 선형검색보다 조건판단횟수가 훨씬 줄음
//배열의 요소의 개수가 n개인 배열 a에서 key와 일치하는 값을 찾음. a의 길이는 n+1
static int seqSearchSentinel(int[] a, int n, int key) {
		int i=0;
        // 배열을 만들때 요소의 개수 + 1개로 만들고 제일 마지막에 key를 저장
		a[n] = key; 
		while(true) {
			if(a[i]==key) {
				break;
			}
			i++;
		}
		return i==n ? -1 : i;
	}