Linear Search와 Binary Search

오늘은 검색 알고리즘에 대해 다뤄보도록 하겠습니다. '검색'이란 단어, 정말 익숙하죠? 

무언가 특정한 데이터를 찾아나갈 때 사용하곤 합니다. 검색의 과정을 정리하며 더 자세하게 설명해보자면 어떠한 특정 항목에 관심이 있고 이는 우리가 주목하고 있는 것입니다. 여기서 이 주목하는 것을 키(key)라고 합니다.

 

 

검색 기법의 종류

 

검색 기법은 다양합니다. 우리는 각 기법의 장단점을 고려하여 알고리즘을 선택해야 합니다. 

배열을 활용한 검색 알고리즘에는 일반적으로 세 가지 방법이 있습니다.

- Linear Search : 무작위로 늘어놓은 데이터 모임에서 검색을 수행

- Binary Search : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행

- Hash : 추가 / 삭제가 빈번하게 일어나는 데이터 모임에서 아주 빠른 검색을 수행

 

 

Linear Search(선형 검색)

 

Linear search란?

우선 Linear Search란 요소가 직선 모양으로 늘어선 배열에서 원하는 값을 찾기 위해 0번째 인덱스부터 배열의 끝까지 순차적으로 요소를 검색하는 것입니다. 따라서 Sequential Search(순차 검색)라고도 합니다.

 

배열의 요소를 순차적으로 검색하는 선형 검색의 종료 조건을 두 가지 입니다.

    1. 검색에 실패한 경우(검색한 값을 발견하지 못하고 배열의 끝을 지나간 경우)

    2. 검색에 성공한 경우(검색할 값과 같은 요소를 발견한 경우)

 

 

 

시간복잡도

Linear Search의 시간복잡도를 알아봅시다. 

 

1. 최악의 경우

배열 요소수가 n개일 때, 최악의 경우에 해당하는 비교연산 횟수는 n입니다. 

따라서 데이터 수 n에 대한 연산 횟수의 함수 T(n)은 T(n) = n 입니다.

 

2. 평균적인 경우

배열의 첫 요소부터 마지막 요소까지 검색 대상이 존재할 확률은 동일합니다. 탐색 대상이 존재하지 않는 경우의 연산 횟수는 n이고 탐색 대상이 존재하는 경우의 연산횟수는 n/2입니다.

 

따라서 Linear Search의 평균적인 경우의 시간복잡도 함수는 T(n) = 3n/4입니다.

 

여기서 구현한 평균적인 경우의 시간복잡도 계산은 탐색 대상이 존재할 확률이 50%보다 높을 수도, 낮을 수도 있기 때문에 신뢰도가 높지 않습니다. 그러므로 최악의 경우(n)를 시간복잡도의 기준으로 삼습니다.

 

 

 

Linear Search의 구현

자바로 구현한 코드는 다음과 같습니다.

 

import java.util.Scanner;

public class LinearSearch {
	
	public static int LinearSearch(int[] x, int n, int key) {
		
		for(int i=0;i<n;i++) {
			if(x[i]==key) {
				return i;
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		
		System.out.print("요소 개수 : ");
		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		
		int[] array = new int[num];
		for(int i=0; i<num ; i++) {
			System.out.print("array["+i+"] : ");
			array[i]=scan.nextInt();
		}
		
		System.out.print("검색할 값 : ");
		int key = scan.nextInt();
		
		int index = LinearSearch(array, num, key);
		if(index==-1) {
			System.out.println("찾는 값이 없습니다");
		}
		else {
			System.out.printf("해당 값은 x[%d]에 있습니다\n", index);
		}
	}
	
}

 

 

 

Binary Search(이진 검색)

 

 

Binary Search란?

Binary Search는 정렬된 데이터를 반으로 나누어서 검색하고자 하는 Key가 포함된 부분을 결정한 후, 해당 부분을 또 다시 나누어서 검색하는 방식을 반복하여 Key를 찾는 검색 방법입니다.

 

 

 

시간복잡도

 

Binary Search는 퀵정렬과 유사하게 Divide and Conquer(분할 후 정복)의 전략을 사용합니다. 이 전략을 사용하는 알고리즘은 문제를 나누어 해결해 나가는 방법이기 때문에 실행 시간은 log의 성질을 갖습니다. 특히 문제의 크기를 정확히 양분하는 경우에는 최악의 경우 logN의 성능을 보장합니다.

 

Binary Search의 탐색시간은 T(N) = K * logN으로 O(logN)입니다. Linear Search의 탐색시간보다 상당히 빠르지만 Binary Search는 반드시 정렬이 되어있어야 합니다. 그러므로 정렬되지 않는 리스트의 경우에는 정렬하는 비용 또한 상당히 들 것입니다.

 

 

이와 같은 단점에도 불구하고 다음과 같은 상황에서 Binary Search는 효율적인 성능을 제공합니다.

 

    1. 새로운 자료가 추가되었어도 모든 자료가 재정렬이 일어나지 않는 경우 - 해싱, 인덱스를 사용하는 경우

    2. 획기적으로 빠르고 효율적인 자료의 재정렬이 가능한 자료구조를 사용할 경우 - Binary Tree 계열의 트리 사용 

 

 

 

Binary Search의 사용

Arrays API에 binarySearch() 함수가 있습니다. 이 함수는 음수값을 반환하는 경우가 있어 우리가 일반적으로 구현하는 방식과 차이가 조금 있습니다.

 

우리가 검색하는 데이터가 딱 맞게 존재하는 경우에는 양수가 반환되지만 정확히 같은 값이 아니라면 배열에서 자기 위치를 찾아(배열에 없음에도 불구하고) 음수로 반환한다는 특징이 있습니다. 주의합시다!

 

 

 

Binary Search의 구현 

자바로 작성한 코드는 다음과 같습니다.

   - 배열 안에 있는 모든 원소가 정렬된 상태에서 동작하도록 해야 합니다 !

     자바에서는 util 패키지에서 Arrays와 Collections를 활용해 내장 정렬함수를 지원합니다

   - high / low / mid 의 위치를 바꿔주며 Key를 찾아내도록 합니다

 

* 위에 구현한 LinearSearch를 기반으로 수정해주었습니다.

 

 

import java.util.Scanner;
import java.util.Arrays;

public class BinarySearch {
	
	public static int BinarySearch(int[] x, int n, int key) {
		
		Arrays.sort(x);
		int high = n-1;
		int low = 0;
		
		while(low<=high) {
			
			int mid = (int)((low+high) / 2);
			
			if(x[mid] == key) return mid;
			
			else if(x[mid] < key) {
				low = mid+1;
				mid = (int)((low+high) / 2);
			}
			else {
				high=mid+1;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		
		System.out.print("요소 개수 : ");
		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		
		int[] array = new int[num];
		for(int i=0; i<num ; i++) {
			System.out.print("array["+i+"] : ");
			array[i]=scan.nextInt();
		}
		
		System.out.print("검색할 값 : ");
		int key = scan.nextInt();
		
		int index = BinarySearch(array, num, key);
		if(index==-1) {
			System.out.println("찾는 값이 없습니다");
		}
		else {
			System.out.printf("해당 값은 x[%d]에 있습니다\n", index);
		}
	}
	
}