[Algorithm] 탐색 알고리즘 (이진 탐색 알고리즘)

탐색 알고리즘

탐색 알고리즘

• 어떤 데이터 구조 안에 저장되어 있는 정보를 구하는 알고리즘
  • 배열에서 가장 큰 값 찾기
  • 데이터 베이스에서 레코드 하나 읽어오기
  • 배낭 문제 등

대표적인 탐색 알고리즘

• 선형(linear) 탐색 알고리즘

  

  
  
  • 모든 데이터에 사용 가능
  • 모든 index를 처음부터 하나씩 검색하면서 찾는 방법
  • 시간복잡도: O(N)
  • N 만큼의 용량이 필요

• 해시 맵을 이용한 탐색

  

  
  
  • 모든 데이터에 사용 가능
  • 입력값의 나머지연산의 결과값을 index 로 사용하여 검색하는 방식
  • 시간복잡도: O(1)
  • N 보다 큰 용량이 필요

이진 탐색

이진 탐색 알고리즘

• 데이터가 정렬되어 있는 배열에서 특정한 값을 찾는 알고리즘

• 이진 탐색 수행과정
  1. 정렬된 데이터의 중간값을 선택
  2. 중간값과 찾고자 하는 목표값을 비교
     1. 목표값 < 중간값 이면, 중간값을 기준으로 좌측의 데이터들을 대상으로 다시 탐색
     2. 목표값 > 중간값 이면, 중간값을 기준으로 오른쪽의 데이터드를 대상으로 다시 탐색
  3. 찾고자 하는 값을 찾을 때까지 1~2 과정을 반복

이진 탐색 알고리즘의 시간 복잡도

• 이진 탐색은 탐색을 시도할 때 마다 탐색 대상의 범위가 절반씩 줄어든다.

• O(logN)

이진 탐색 알고리즘 구현

• 알고리즘 과정
  1. L = 0, R = N-1 로 정의
  2. R ≥ L 일 때까지 반복(L>R 이면 종료)
  3. M = (L+R)/2 로 정의
  4. 만약 number(M) > value 면, R = M-1
  5. 만약 number(M) < value 면, L = M+1
  6. 만약 number(M) == value 면, 검색 성공 M 반환

1. 반복문으로 구현

   package algorithm;
   
   public class Main {
   
   	public static void main(String[] args) {
   		// TODO Auto-generated method stub
   		int sortedArray[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   		
   		int result = binarySearch(sortedArray, 4);
   		
   		System.out.println("찾고자 하는 index 는 " + result + "이다.");
   	}
   	
   	public static int binarySearch(int sortedArr[], int value) {
   		//1. L, R 선언
   		int L = 0;
   		int R = sortedArr.length-1;
   		while(R >= L) {
   			int M = (L+R)/2;
   			if(sortedArr[M] > value) { 
   				R = M-1; 
   			}
   			if(sortedArr[M] < value) {
   				L = M+1;
   			}
   			if(sortedArr[M] == value) {
   				return M;
   			}
   		}
   		
   		return 0;
   	}
   	
   }

2. 재귀함수로 구현

   package algorithm;
   
   public class Main {
   
   	public static void main(String[] args) {
   		// TODO Auto-generated method stub
   		int sortedArray[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   		
   		int result = binarySearchRecursive(sortedArray, 4, 0, 9);
   		
   		System.out.println("찾고자 하는 index 는 " + result + "이다.");
   	}
   	
   	public static int binarySearchRecursive(int sortedArr[], int value, int L, int R) {
   		int M = (L+R)/2;
   		
   		if(sortedArr[M] < value){
   			int left = M+1;
   			return binarySearchRecursive(sortedArr, value, left, R);
   		}else if(sortedArr[M] > value) {
   			int right = M-1;
   			return binarySearchRecursive(sortedArr, value, L, right);
   		}
   
   		return M;
   	}
   
   }