[알고리즘-02] 검색 - 선형 검색, 이진 검색

1. 검색(Searching)

- 키(key)를 이용하여 원하는 데이터를 찾는 것

 

- 배열 검색을 위한 알고리즘

1) 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행

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

3) 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행

   (1) 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법

   (2) 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

 

- 데이터 집합에 대한 검색뿐 아니라 데이터의 추가, 삭제 등 다른 작업까지 고려해야 함

- 용도, 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택하기

 

---

 

2. 선형 검색(Linear search)

1) 선형 검색이란?

- 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞에서부터 순서대로 요소를 검색하는 것

 

 

- 다음 조건 중 하나라도 성립하면 검색을 종료함

 

조건 1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패
조건 2. 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공

 

 

- 배열의 요솟수가 n개일 때 조건 1,2를 판단하는 횟수의 평균값은 n / 2

- 선형 검색은 배열에서 순서대로 검색하는 유일한 방법임

 

 

2) 보초법(sentinel method)

- 선형 검색에서 종료 조건을 검사하는 비용을 반(50%)으로 줄이는 방법

- 검색하고자 하는 키 값을 맨 끝 요소, 즉 보초(sentinel)에 저장

 

 

조건 1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패
조건 2. 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공

 

- 원하는 데이터가 존재하지 않아도 보초까지 검색하면 조건 2가 성립함

- 조건 1을 판단하지 않게 되면서 반복문에서 종료 판단 횟수를 2회에서 1회로 줄임 (50% 감소)

 

 

 

---

 

 

3. 이진 검색(binary search)

1) 이진 검색이란?

- 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

 

ex) 48을 이진 검색할 때

 

(1) 배열의 중앙에 위치한 요소인 a[3]부터 검색을 시작

 

(2) 31은 48보다 작으므로 검색 대상을 a[4]~a[6]으로 좁힘. 그 중 중앙에 위치한 요소인 a[5]부터 검색

(3) 53은 48보다 크므로 검색 대상을 a[4]로 좁힘. a[4]가 48이므로 검색 성공

 

2) 검색 범위 좁히는 법

 

pl : 맨 앞 인덱스
pr : 맨 끝 인덱스
pc : 중앙 인덱스
key : 찾을 값
a[] : 값이 있는 배열

 

 

(1) a[pc] < key

- a[pl]~a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외

- 검색 범위는 a[pc]보다 뒷쪽인 a[pc+1]~a[pr]

- pl = pc + 1로 업데이트

 

(2) a[pc] > key

- a[pc]~a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외

- 검색 범위는 a[pc]보다 앞쪽인 a[pl]~a[pc-1]

- pr = pc - 1로 업데이트

 

 

- 종료 조건

 

조건 1. a[pc]와 key가 일치하는 경우 -> 검색 성공
조건 2. 검색 범위가 더 이상 없는 경우 -> 검색 실패

 

- 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n

---

 

 

4. 선형 검색과 이진 검색의 복잡도

1) 복잡도(complextiy)

- 알고리즘의 성능을 객관적으로 평가하는 기준

(1) 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것

(2) 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

- O(f(n))과 O(g(n))의 복잡도를 계산하는 법

 

O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

 

즉, 전체 복잡도는 차원이 가장 높은 복잡도를 의미함

 

2) 선형 검색의 시간 복잡도

static int seqSearch(int[] a, int n, int key) {
    int i = 0;				// O(1)
    while(i < n) { 			// O(n/2)
   	    if(a[i] == key)		// O(n/2)
        	return i;		// O(1)
        i++;				// O(n/2)
    }
    
    return -1;				// O(1)
}

 

※ 컴퓨터에게 n/2와 n의 차이는 크지 않다?

- n의 값이 무한히 커진다고 가정했을 때, n/2와 n의 차이는 무의미해지기 때문에 컴퓨터는 n/2를 n으로 인식함

 

O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(n)

 

선형 검색 알고리즘의 복잡도는 O(n)

 

 

3) 이진 검색의 시간 복잡도

static binSearch(int[] a, int n, int key) {
    int pl = 0;				// O(1)
    int pr = n - 1;			// O(1)
    
    
    do {		 				
    	int pc = (pl + pr) / 2;		// O(log n)
   	if(a[pc] == key)		// O(log n)
    	    return pc;			// O(1)
        else if(a[pc] < key)		// O(log n)
            pl = pc + 1;		// O(log n)
        else					
            pr = pc - 1;		// O(log n)
    } while(pl <= pr);			// O(log n)
    
    return -1;				// O(1)
}

 

 

O(1) + O(1) + O(log n) + O(log n) + O(1) + O(log n) + ... + O(1) = O(log n)

 

이진 검색 알고리즘의 복잡도는 O(log n)

 

 

 

5. Arrays.binarySearch에 의한 이진 검색

1) Arrays.binarySearch

- Array는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공

- javas.util.Arrays 클래스의 binarySearch 메서드 제공

- 이진 검색 메서드를 직접 코딩할 필요가 없고, 모든 자료형 배열에서 검색이 가능함

- 오름차순으로 정렬된 배열 a를 가정하고 키 값이 key인 요소를 이진 검색함

 

- javas.util.Arrays의 binarySearch 메서드 (출처 : docs.oracle.com/javase/8/docs/api/)

 

static int	binarySearch(byte[] a, byte key) Searches the specified array of bytes for the specified value using the binary search algorithm.
static int	binarySearch(byte[] a, int fromIndex, int toIndex, byte key) Searches a range of the specified array of bytes for the specified value using the binary search algorithm.
static int	binarySearch(char[] a, char key) Searches the specified array of chars for the specified value using the binary search algorithm.
static int	binarySearch(char[] a, int fromIndex, int toIndex, char key) Searches a range of the specified array of chars for the specified value using the binary search algorithm.
static int	binarySearch(double[] a, double key) Searches the specified array of doubles for the specified value using the binary search algorithm.
static int	binarySearch(double[] a, int fromIndex, int toIndex, double key) Searches a range of the specified array of doubles for the specified value using the binary search algorithm.
static int	binarySearch(float[] a, float key) Searches the specified array of floats for the specified value using the binary search algorithm.
static int	binarySearch(float[] a, int fromIndex, int toIndex, float key) Searches a range of the specified array of floats for the specified value using the binary search algorithm.
static int	binarySearch(int[] a, int key) Searches the specified array of ints for the specified value using the binary search algorithm.
static int	binarySearch(int[] a, int fromIndex, int toIndex, int key) Searches a range of the specified array of ints for the specified value using the binary search algorithm.
static int	binarySearch(long[] a, int fromIndex, int toIndex, long key) Searches a range of the specified array of longs for the specified value using the binary search algorithm.
static int	binarySearch(long[] a, long key) Searches the specified array of longs for the specified value using the binary search algorithm.
static int	binarySearch(Object[] a, int fromIndex, int toIndex, Object key) Searches a range of the specified array for the specified object using the binary search algorithm.
static int	binarySearch(Object[] a, Object key) Searches the specified array for the specified object using the binary search algorithm.
static int	binarySearch(short[] a, int fromIndex, int toIndex, short key) Searches a range of the specified array of shorts for the specified value using the binary search algorithm.
static int	binarySearch(short[] a, short key) Searches the specified array of shorts for the specified value using the binary search algorithm.
static <T> int	binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c) Searches a range of the specified array for the specified object using the binary search algorithm.
static <T> int	binarySearch(T[] a, T key, Comparator<? super T> c) Searches the specified array for the specified object using the binary search algorithm.

 

(1) 검색에 성공한 경우

- key와 일치하는 요소의 인덱스를 반환

- 이 때, 맨 앞의 인덱스나 특정한 인덱스가 아닌 무작위의 인덱스 반환

 

(2) 검색에 실패한 경우

- 삽입 포인트를 x라고 할 때 -x-1을 반환

- 삽입 포인트 : 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스

 

 

2) 기본 자료형 배열에서 binarySearch 메서드 사용

int[] x = {15, 27, 39, 77, 92, 108, 121};
int key1 = 39;
int key2 = 103;

int idx1 = Arrays.binarySearch(x, key1);	// idx1 = 2 (검색 성공시 인덱스 반환)
int idx2 = Arrays.binarySearch(x, key2);	// idx2 = -6 (검색 실패시 -(삽입포인트)-1 반환, 즉 -5-1 = -6 반환)

- 배열 x는 오름차순으로 정렬되어 있어야 함

 

3) 객체의 배열에서 binarySearch 메서드 사용

(1) static int binarySearch(Object[] a, Object key)

- '자연 정렬'이라는 방법으로 요소의 대소 관계를 판별

- 정수 배열, 문자열 배열에서 검색할 때 적절

 

(2) static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

- '자연 순서'가 아닌 순서로 줄지어 있는 배열에서 검색하거나 '자연 순서'를 논리적으로 갖지 않는 클레스 배열에서 검색할 때 적절

- 배열의 요소가 어떤 순서로 줄지어 있는지, 각 요소의 대소 관계를 어떻게 판단할 것인지에 대해서 알려주어야 하며, 이것이 세 번째 매개변수 c임

- 즉, Comparator 인터페이스와 compare 메서드를 구현한 클래스를 먼저 작성한 뒤, 그 클래스의 인스턴스를 생성하여 c로 전달함

 

 

 

 

 

 

참고 - Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 (저자 : 보요 시바타, 출판 : 이지스 퍼블리싱)