배열 원소 검색으로 값 찾는 방법(선형 검색, 이진 검색, 피보나치 검색)

선형 검색을 사용하여 정렬되지 않은 배열에서 검색

정렬되지 않은 배열에서는 첫번째 요소에서 마지막 요소까지 선형 순회를 통해 검색 작업을 수행할 수 있습니다.

public class UnsortedLinearSearch {
	public static void main(String[] args) {
		int arr[] = { 12, 34, 10, 6, 40 };
        int n = arr.length;
        
        int key = 40;
        
        int position = findElement(arr, n, key);
        System.out.println(position);
	}
	
	static int findElement(int arr[], int n, int key) {
		for(int i = 0; i < n; i++) {
			if(arr[i] == key) return i;
		}
		return -1;
	}
}

 

이진 검색을 사용하여 정렬된 배열에서 검색

정렬된 배열에서 이진 검색을 사용하여 검색 작업을 효율적으로 수행할 수 있습니다.

public class SortedBinarySearch {

	public static void main(String[] args) {
		int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
		int n = arr.length - 1;
		int key = 11;
		
		int index = binarySearch(arr, 0, n, key);
		System.out.println(index);
	}
	
	static int binarySearch(int arr[], int low, int high, int key) {
		if(high < low) return -1;
		
		int mid = (low + high) / 2;
		if(key == arr[mid]) return mid;
		if(key > arr[mid]) return binarySearch(arr, mid + 1, high, key);
		return binarySearch(arr, low, mid - 1, key);
	}

}

low와 high는 배열의 시작 인덱스와 마지막 인덱스를 나타냅니다.

중간 요소와 비교하여 낮으면 왼쪽그룹에서 높으면 오른쪽 그룹에서 검색하면서 찾아냅니다.

 

피보나치 검색을 사용하여 정렬된 배열에서 검색

package array;

public class FibonacciSearch {
	
	static int fibonacciSearch(int arr[], int x, int n) {
		int fibMMm2 = 0;
		int fibMMm1 = 1;
		int fibM = fibMMm2 + fibMMm1;
		int offset = -1;
		
		while(fibM < n) {
			fibMMm2 = fibMMm1;
			fibMMm1 = fibM;
			fibM = fibMMm2 + fibMMm1;
		}
		
		while(fibM > 1) {
			int i = Math.min(offset + fibMMm2, n - 1);
			if(arr[i] < x) {
				fibM = fibMMm1;
				fibMMm1 = fibMMm2;
				fibMMm2 = fibM - fibMMm1;
				offset = i;
			} else if(arr[i] > x) {
				fibM = fibMMm2;
				fibMMm1 = fibMMm1 - fibMMm2;
				fibMMm2 = fibM - fibMMm1;
			} else {
				return i;
			}
		}
		
		if(fibMMm1 == 1 && arr[n-1] == x) return n - 1;
		
		return -1;
	}
	
	public static void main(String[] args) {
		int arr[] = { 5, 10, 22, 35, 40, 45,  50,
                80, 82, 85, 90, 100, 235 };
		int n = arr.length;
		int x = 5;
		
		int offset = fibonacciSearch(arr, x, n);
		System.out.println(offset);
	}
}

피보나치 수열을 이용해 이진 검색과 유사한 방식으로 진행합니다.

배열의 길이를 가지고 길이만큼 피보나치의 값을 찾고

찾는 값이 키보다 크면 큰 값을 다 버리고 2단계 전으로 가는것이고

찾는 값이 키보다 작으면 작은 값을 버리고 1단계 전으로 가면서 오프셋을 증가시킵니다.

피보나치 수열이 배열의 길이와 딱 맞을때 마지막 값을 찾기 위해서 while문 끝난 뒤 if문을 통해 마지막 값을 비교해 봅니다.