보간 탐색이란?

· 정렬이 이미 되어 있는 리스트에서 탐색키가 존재할 위치를 예측하여 탐색하는 방법. (사전에서 'ㄱ'으로 시작되는 단어가 앞에 있을 거라고 생각하고 앞 부분을 찾는 것과 같은 원리)

· 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색함. (이진 탐색의 업그레이드 버전?)

보간 탐색의 index값 구하는 공식

이진 탐색에서 mid값 구하는 공식과는 다름.

보간 탐색의 장점

· 많은 데이터가 비교적 균등하게 분포되어 있을 경우 보간 탐색은 이진 탐색보다 더 효율적일 수 있음.

시간 복잡도

보간 탐색 코드(Java)

public int interpolationSearch(int[] arr, int key, int low, int high) {
	int index = 0;
	
	while(low < high) {
		if(key < arr[low] || key > arr[high]) {
			return -1;
		} 
			
		index = low + (key - arr[low]) * ((high - low)) / (arr[high] - arr[low]);
			
		if(key == arr[index]) {
			return index;
		} else if(key < arr[index]) {
			high = index - 1;
		} else {
			low = index + 1;
		}
	}
		
	return -1;
}

이진 탐색이란?

· 정렬된 리스트의 중앙에 있는 키 값을 조사하여 찾고자하는 레코드가 왼쪽에 있는지 오른쪽에 있는지를 알아내어 탐색의 범위를 반으로 좁혀가는 방법.

· 반드시 정렬된 리스트여야 하며 고정된 데이터에 적합하다. 따라서 데이터의 삽입이나 삭제가 빈번할 시에는 적잡하지 않다.

이진 탐색의 비교 횟수

시간 복잡도

이진 탐색 코드 (Java)

public void binarySearch(int[] array, int num) {
	int left = 0;
	int right = array.length - 1;
	int mid = 0;
		
	while(left <= right) {
		mid = (left + right) / 2;
			
		if(num == array[mid]) {
			System.out.println("찾으시는 숫자 " + num + "을 찾았습니다. " + (mid + 1) + "번째에 있었습니다.");
			break;
		} else if(num < array[mid]) {
			right = mid - 1;
			mid = (left + right) / 2;
		} else {
			left = mid + 1;
			mid = (left + right) / 2;
		}
	}
}

순차 탐색이란?

· 정렬되지 않은 레코드를 처음부터 마지막까지 하나씩 검사하여 원하는 레코드를 찾아가는 방법.

· 단 방향으로 탐색하기 때문에 선형 탐색이라고 함.

순차 탐색의 장점

· 별도의 데이터 조작이 없으므로 구현이 쉬움

순차 탐색의 단점

· 비 효율적인 방법

순차 탐색의 평균 비교횟수

시간복잡도

· 탐색이 성공할 경우 비교 횟수 :

· 탐색이 실패할 경우 비교 횟수 :

따라서

순차 탐색 코드 (Java)

public int sequentialSearch(int[] arr, int key) {
	for(int i = 0; i < arr.length; i++) {
		if(arr[i] == i) {
			return i;
		}
	}
		
	return -1;
}

탐색이란?

· 배열, 트리, 그래프, 파일, 데이터베이스, 인터넷 등에 저장되어 있는 많은 자료 중에서 필요한 자료를 찾는 것.

· 레코드의 집합에서 특정한 레코드를 찾아내는 작업. (레코드들은 보통 키라고 불리는 특정 필드에 의해 식별)

탐색의 종류

· 순차 탐색, 색인 순차 탐색, 이진 탐색, 보간 탐색, 블록 탐색, 피보나치 탐색 등 그 종류가 다양함.

탐색의 성능 향상

· 무작위의 상태보다는 어느 정도 분류가 되어 있는 상태이거나 정렬된 상태일 경우 탐색이 더 용이.