선형검색, 이진검색, 해시법

개요

 

데이터 집합에서 특정 값을 가진 요소를 찾아내는 작업이 검색인데 기본적인 검색 법으로 선형검색, 이진검색, 해시법에 대해 정리해본다. 검색 작업은 결국 비용이 들어가기 때문에 가능한 저렴한 비용의 검색법을 적용해야 하는데 어떤 검색법이 적절할지는 자료구조에 따라 다를 수 있다. 

 

 각 검색법의 적절한 활용법은 아래와 같다.

선형 검색  -  무작위의 데이터 집합에서 검색을 수행할 경우

이진 검색  -  일정한 규칙으로 정렬되어 있는 데이터 집합에서 검색을 수행할 경우

해시법      -  추가, 삭제가 자주일어나는 경우

 

 

선형 검색

 

모든 데이터를 하나씩 확인하는 가장 기본적인 검색 방법. 원하는 데이터를 찾을때까지 검색을 수행하기 때문에 최대 n의 복잡도를 같는다. 성능향상을 위해 보초법을 적용하면 비용을 절약할 수 있다.

 기본적으로 선형 검색에서는 모든 데이터를 처음부터 마지막 데이터까지 하나씩 선택하며 검색하며 아래 과정으로 실행한다.

 

 1. 데이터집합에서 마지막 데이터까지 검색을 다 해봤는지 확인한다.

 2. 현재 선택된 데이터가 찾는 데이터인지 확인한다.

 3. 1,2를 반복하며 마지막까지 찾는 데이터가 없다면 데이터 집합에 해당 데이터가 없으므로 검색을 종료한다.

 

위 방법으로 선형검색을 실행하면 데이터의 1,2 과정에서 매번 if문을 호출해야하기 때문에 최대 데이터갯수*2 번의 if문을 실행해야 한다.  이 비용을 줄이기 위한것이 보초법인데, 보초법은 아래와 같이 실행한다.

 

 1. 데이터 집합 마지막에 찾는 데이터를 삽입한다.

 2. 매번 현제 데이터가 찾는 데이터인지 확인한다.

 3. 찾는 데이터가 발견되면 해당 데이터의 인덱스를 확인하고, 해당 인덱스가 마지막이라면 찾는 데이터가 없는 것으로 검색을 종료한다.

    (마지막 인덱스에 존재하는 데이터는 데이터 집합에 존재하던 것이 아니라 1. 과정에서 삽입한 데이터이다.)

 

선형 검색 예제

import java.util.Scanner;

public class SeqSearchSen {

	static int seqSearchSen(int[] arr, int num, int key) {
		int i=0;
        
        	while(true) {
			if(i==num) {
				return -1;
			}
			if(arr[i] == key) {
				return i;
			}
			i++;
		}
        
        	/* 보초법을 활용한 경우
		for(; i<arr.length; i++) {
			if(arr[i]==key) {
				break;
			}
		}*/
        
		return (i==num)? -1 : i;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.print("배열의 길이를 입력하세요 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] arr = new int[num+1];
		
		for(int i=0; i<arr.length-1; i++) {
			System.out.print((i+1)+"번째 값 : ");
			arr[i] = Integer.parseInt(sc.nextLine());
		}
		
		System.out.print("검색할 값 : ");
		int key = Integer.parseInt(sc.nextLine());
		arr[num] = key;
		
		int result = seqSearchSen(arr,num,key);
		if(result==-1) {
			System.out.println("찾는 값이 없습니다.");
		} else {
			System.out.println(key+"은(는) "+(result+1)+"번째에 있습니다.");
		}
		
		
		
		sc.close();
	}

}

 

 

이진 검색

 

이진검색의 전제조건은 상술한대로 정렬이 되어 있다는 점인데, log n의 복잡도를 갖기 때문에 비용이 훨씬 저렴하다.

검색 방법은 아래와 같다.

 

 1. 정렬이 되어있기 때문에 최소, 최대값은 index 0와 끝번호이다. 이 두 값과 중앙값 = (최소+최대)/ 2 을 저장한다.

 2. 찾는 값과 중앙값을 비교해서

  2-1. 찾는 값이 중앙값 보다 크다면 최소값 인덱스를 중앙값+1로 갱신한다.

  2-2. 찾는 값이 중앙값보다 작다면 최대값 인덱스를 중앙값-1로 갱신한다.

 3. 1,2 과정을 반복하다가 최소값>최대값의 상황이 발생하면 데이터 집합에 찾는 데이터가 없는 경우로 검색을 종료한다.

 

이진 검색 예제 코드

 

import java.util.Scanner;

public class BinSearch {

	static int binSearch(int[] arr, int num, int key) {
		int pl = 0;
		int pr = num-1;
		int pc;
		while(pl<=pr) {
			pc = (pr+pl)/2;
			if(arr[pc]==key) {
				return pc;
			} else if(arr[pc]>key) {
				pr = pc-1;
			} else {
				pl = pc+1;
			}
		}
		return -1;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		System.out.print("배열의 길이를 입력하세요 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] arr = new int[num];
		
		System.out.println("값을 오름차순으로 입력하세요.");
		System.out.print("1번째 값 : ");
		arr[0] = Integer.parseInt(sc.nextLine());
		
		for(int i=1; i<arr.length; i++) {
			System.out.print((i+1)+"번째 값 : ");
			arr[i] = Integer.parseInt(sc.nextLine());
			
			while(arr[i]<arr[i-1]) {
				System.out.println("이전 보다 큰 값을 입력하세요.");
				System.out.print((i+1)+"번째 값 : ");
				arr[i] = Integer.parseInt(sc.nextLine());
			}
		}
		
		System.out.print("검색할 값을 입력하세요 : ");
		int key = Integer.parseInt(sc.nextLine());
		
		int result = binSearch(arr, num, key);
		if(result==-1) {
			System.out.println("찾는 값이 업습니다.");
		} else {
			System.out.println(key+ "은(는) "+ (result+1) + "번째에 있습니다.");
		}
		
		sc.close();
	}

}