Search(검색, 탐색) _ Sequential Search, Binary Search

1. Search(검색, 탐색)이란?

- 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업

- 원하는 항목 : 목적하는 "탐색키(Search Key)"를 가진 항목

 

 

 

 

 

 

 

2. Search 1 > Sequential Search(순차 검색)

: 일렬로 된 자료를 순서대로 검색

- Array, Linked List와 같은 순차 자료구조 활용

 

(1) 정렬되지 않은 자료

[과정]

① 첫 번째 원소부터 순서대로 검색대상과 키 값을 비교

② 키 값과 동일한 원소 찾음 → 해당 원소의 인덱스 반환

③ 마지막까지 찾지 못함 → '검색 실패' 반환

 

[비교횟수 및 시간복잡도]

- 평균 비교횟수 = (1+2+3+ ... + (n-1) + n) / n = (n+1) / 2

- 시간 복잡도 = O(n)

 

public static boolean unorderedSearch(int[] arr, int t) {
	boolean answer = false;
	for(int i = 0; i < arr.length; i++) { // O(n)의 시간복잡도
		if(arr[i] == t) {
			answer = true;
			break;
		}
	}
	return answer;
}

 

 

 

(2) 정렬된 자료

[과정 (가정 : 오름차순)]

① 첫 번째 원소부터 순서대로 검색대상과 키 값을 비교

② 키 값과 동일한 원소 찾음 → 해당 원소의 인덱스 반환

③ 원소의 키 값 > 검색 대상의 키 값 → '검색 실패' 반환

 

[비교횟수 및 시간복잡도]

- 평균 비교횟수 = (1 + 2 + ... + k + k + k) / n (검색 대상 k보다 큰 수에 대해서는 더이상 탐색 X)

- 시간 복잡도 = O(n)

 

public static boolean orderedSearch(int[] arr, int t) {
	boolean answer = false;
	Arrays.sort(arr);
	for(int i = 0; i < arr.length; i++) { // O(n)의 시간복잡도
		if(arr[i] == t) {
			answer = true;
			break;
		}
		else if(arr[i] > t)	break;
	}
	return answer;
}

 

 

 

 

 

 

3. Search 2 > 이진 검색(Binary Search)

: 자료의 가운데에 있는 항목의 키 값과 비교 후 다음 검색 위치 결정 (검색 범위를 반으로 줄임)

※ 단, 정렬된 자료일 때만 사용 가능

[과정]

① 자료의 중앙 원소 선택 : (start + end) / 2

② 목표값 == 중앙원소 → 해당 원소의 인덱스 반환

    목표값 < 중앙원소 → 자료의 왼쪽 절반에 대해서 검색 수행

    목표값 > 중앙원소 → 자료의 오른쪽 절반에 대해서 검색 수행

③ 더 이상 남은 범위가 없으면 '검색 실패' 반환

 

[비교횟수 및 시간복잡도]

- 시간복잡도 = O(루트n) ???

 

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

public class BinarySearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array = new int[] {2, 3, 7, 8, 10, 16, 20, 29};
		Arrays.sort(array);
		Scanner sc = new Scanner(System.in);
		int target = sc.nextInt();
		System.out.println(binarySearch(array, target));
	}
	
	public static int binarySearch(int[] arr, int t) {
		int start = 0; int end = arr.length;
		int mid = 0;
		int answer = -1;
		
		while(start <= end) {
			mid = (start + end) / 2;
			if(arr[mid] == t) {
				answer = mid;
				break;
			}
			else if(arr[mid] < t)	start = mid + 1;
			else	end = mid-1;
		}
		return answer;
	}
}

++ 자바의 Arrays 클래스에서는 int binarySearch(배열, key) 의 형태로 메소드를 제공함

(인덱스를 출력)

 

 

 

 

 

 

 

4. Search 3 > 인덱스

: 키-필드만 가진 배열(인덱스)을 이용

→ 상대적으로 크기가 작은 인덱스 Array를 이용하여 속도 개선

- 데이터베이스 인덱스 설계 원리에 활용