[Java] 탐색 알고리즘

 

😚탐색 알고리즘

탐색 알고리즘은 데이터 집합에서 특정 데이터를 찾는데 사용된다. 이는 데이터 검색, 경로 탐색, 최적화, 그래프 분석등 다양한 분야에서 활용되며 문제의 복잡성이나 데이터 구조 등에 따로 적절한  알고리즘을 선택해야 한다.

 

😦종류

탐색알고리즘은 대표적으로 선형 탐색, 이진 탐색, 깊이 우선 탐색, 너비 우선 탐색등이 있다!

이번 글에서는 선형 탐색과 이진 탐색을 정리 해보려고 한다.

📌선형 탐색( Linear Search )

• 간단하고 직관적인 방법으로, 구현이 쉽다는 장점이 있지만 배열의 크기가 크면 시간이 오래걸리는 단점이 있다.
• 왼쪽부터 오른쪽으로 차례로 탐색하는 방법
• 최악의 경우 마지막까지 탐색해야 하기 때문에 시간 복잡도는 O(N)

public class LinearSearch {

	public static void main(String[] args) {
		int arr[] = {1,5,3,6,7,8,9,2,4};
		int target = 7;
		int result = -1;
		
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] == target) {
				result = i;
				break;
			}
		}
		
		if(result != -1) {
			System.out.println(target + "은 배열의 " + result +"번째에 위치합니다.");
		}else {
			System.out.println(target + "은 배열에 존재하지 않습니다.");
		}
		
	}
}

☝  0번 인덱스부터 차례로 탐색후 7을 찾게되면 break문으로 빠져 나가게 된다.

 

 

📌 이진 탐색 (Binary Search)

• 배열을 반으로 나누어 찾는 값이 중간 값보다 크면 오른쪽을 작으면 왼쪽을 탐색한다.
• 정렬되어 있는 데이터에 사용

public class BinarySearch {
	
	public static void main(String[] args) {
		int[] arr = {1,2,3,4,5};
		int target = 4;
		int left = 0;
		int right = arr.length - 1;
		int result = -1;
		
		while(left <= right) {
			int mid = left + (right - left) / 2;
			
			if(arr[mid] == target) {
				result = mid;
				break;
			}else if (arr[mid] < target) {
				left = mid + 1;
			}else {
				right = mid - 1;
			}
		}
		
		if(result != -1) {
			System.out.println(target + "은 배열의 " + result +"번째에 위치합니다.");
		}else {
			System.out.println(target + "은 배열에 존재하지 않습니다.");
		}
	}

}

☝  중간값인 3보다 찾는값인 4가 더 크기 때문에 오른쪽을 차례로 탐색한다 !