[배열 검색] 선형 검색, 보초법

 

 

 

 

이번 포스팅 글에서는 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘을 알아보겠다.

 

이 알고리즘을 선형 검색이라고 한다.

 

 

선형 검색의 정의

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞에서부터 순서대로 요소를 비교(검색)를 한다. 이것을 선형 검색(Linear Search)또는 순차 검색(Sequential Search)라고 한다.

 

 

---

선형 검색 기본적인 알고리즘

 

static boolean SerchMethod(int[] arr, int n, int key) {
		int i = 0;

		while (true) {
			if (i == n) { // i==n이 같다는 것은 키 값과 같은 요소값을 찾지 못한 것 (검색 실패)
				return false;
			}
			if (arr[i] == key) { // 키 값과 찾으려는 요소값이 같을 시 (검색 성공)
				return true;

			}
			i++;
		}
}

 

쉽게 생각하면 반복문을 통해 찾으려는 요소값과 키 값이 같을 시 검색을 성공했다고 볼 수 있다.

 

 

 

import java.util.Scanner;

public class inheritance {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		do {
			System.out.print("요솟수: ");
			int arr_num = sc.nextInt();
			int[] arr = new int[arr_num];

			for (int i = 0; i < arr.length; i++) {
				System.out.print("arr[" + i + "]: ");
				arr[i] = sc.nextInt();
			}

			System.out.print("검색할 값: ");
			int serchnumber = sc.nextInt();
			int idx = SerchMethod(arr, arr_num, serchnumber);

			if (idx != -1) {
				System.out.println(serchnumber + "은 arr[" + idx + "]에 있습니다.");
			} else {
				System.out.println("그 값의 요소가 없습니다.");
			}
			System.out.println("다시하겠습니까? (예:1/아니요:-1)");
			n = sc.nextInt();
		} while (n != -1);
	}

	static short SerchMethod(int[] arr, int n, int key) {
		short s = 0;

		while (true) {
			if (s == n) { // i==n이 같다는 것은 키 값과 같은 요소값을 찾지 못한 것 (검색 실패)
				return -1;
			}
			if (arr[s] == key) { // 키 값과 찾으려는 요소값이 같을 시 (검색 성공)
				return s;

			}
			s++;
		}
	}

}

 

SerchMethod 메서드는 배열 arr의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색하고 검색한 요소의 인덱스를 반환한다. 만약 key값과 같은 요소가 여러 개이면 처음 발견한 요소의 인덱스를 반화한다.

모든 요소 값이 key값과 같지 않다면 -1을 반환하다.

 

 

위 메서드를 while에서 for문으로 바꾸어보겠다.

 

static short SerchMethod(int[] arr, int n, int key) {
		for(short i=0;i<n;i++) {
			if(arr[i]==key)
				return i;
		}
		return -1;
}

 

---

 

 

지금까지 선형 검색은 매우 비효율적인 코드라고 볼 수 있다. 50% 효율을 더 향상 시킬 수 있는 "보초법" 이라는 것이 있다. 

 

지금까지 작성한 선형 검색 코드는 프로그램이 종료될 수 있는 조건이 2가지 였다.

 

1. 검색할 값을 발견하지 못 하고 배열의 끝을 지나는 경우

2. 검색할 값과 같은 요소를 발견한 경우

 

 

 

보초법이 무엇인지 간단하게 그림과 함께 설명해보겠다.

 

위 그림에서 배열의 요소 arr[0]~arr[5]는 원래 준비해 놓은 데이터이다. 검색하기 전에 검색하고자 하는 값을 배열의 맨 끝 요소 arr[6]에 저장한다. 저장한 값을 보초(sentinel)라고 한다.

 

만약 정수 5를 검색하고자 한다.

5를 검색하기 위해서 arr[6]=5 이런식으로 배열의 마지막 요소에 key값을 임시로 저장시킨다.

 

 

 

🔑 코드

---

import java.util.Scanner;
//보초법
public class Search {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.print("요솟수:");
		int num = sc.nextInt();
		int[] arr = new int[num + 1];

		for (int i = 0; i < num; i++) {
			System.out.print("x[" + i + "]: ");
			arr[i] = sc.nextInt();
		}

		System.out.print("검색할 값: ");
		int ky = sc.nextInt();
		int indexSearch = seqSearch(arr, num, ky);
		if (indexSearch == -1) {
			System.out.println("그 값의 요소값은 없습니다.");
		} else {
			System.out.printf("%d은(는) x[%d]에 있습니다.", ky, indexSearch);
		}

	}

	static int seqSearch(int[] a, int n, int key) {
		a[n] = key;
		int i = 0;
		while (true) {
			if (a[i] == key) { //검색성공!
				break;
			}
			i++;
		}
		return i == n ? -1 : i;
	}

}

while문을 이용한 보초법

 

 

 

 

import java.util.Scanner;

public class Search {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.print("요솟수:");
		int num = sc.nextInt();
		int[] arr = new int[num + 1];

		for (int i = 0; i < num; i++) {
			System.out.print("x[" + i + "]: ");
			arr[i] = sc.nextInt();
		}

		System.out.print("검색할 값: ");
		int ky = sc.nextInt();
		int indexSearch = seqSearch(arr, num, ky);
		if (indexSearch == -1) {
			System.out.println("그 값의 요소값은 없습니다.");
		} else {
			System.out.printf("%d은(는) x[%d]에 있습니다.", ky, indexSearch);
		}

	}

	static int seqSearch(int[] a, int n, int key) {
		a[n] = key;
		int i;
		for (i = 0; i < n; i++) {
			if (a[i] == key)
				break;
		}
		return i == n ? -1 : i;
	}

}

for문을 이용한 보초법

---

 

 

 

 

 

https://ko.wikipedia.org/wiki/%EC%88%9C%EC%B0%A8_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

순차 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

 

 

대표사진

<a href="https://www.flaticon.com/kr/free-icons/" title="연산 아이콘">연산 아이콘  제작자: Flat Icons - Flaticon</a>

https://www.flaticon.com/kr/free-icon/algorithms_1753819