단순 탐색 & 이진 탐색

단순 탐색이란?

  말 그대로 단순한 탐색이다. 내가 1 ~ 100 의 자연수 중에서 50 이란 숫자를 찾게 된다고 가정하자.

그 때 우리는 단순 탐색을 하면 1,2,3,4,5,6,7,8,9... 49 , 50! 이렇게 찾게 되는 것을 단순 탐색이라 한다.

 

위의 예시를 Java 코드로 표현 해보자.

for(int i=1; i<101; i++){
   if( i == 100 ) System.out.println("I FIND " + i + " !!!! " );
}

선형 탐색은 실행 시간이 빅오표시법으로 O(n) 이다.

이진 탐색이란?

  이진(Binary) 라는 뜻은 0,1이라는 것을 보통 말하지만 내가 생각하기엔 상태값에 따라 2개를 나눈거라 생각한다. 이진 탐색은 그 상태값을 high OR low 로 지정되었다. 즉, 1 ~ 100의 자연수 중에서 나는 27이란 숫자를 찾게 된다고 가정하자. 

1. 탐색 범위를 지정한다. -> ( 첫 탐색 범위 : 1 ~ 100 )
2. 탐색 범위에서 mid 값이 data보다 큰 지 작은 지 본다. -> ( 탐색 범위 mid : 50 / data : 27 / result : 크다 )
   1. result : 크다 ) 탐색 범위 1 (low) ~49( mid - 1 = high ) 로 정한다.
   2. result : 작다 ) 탐색 범위  51(mid +1 = low) ~ high ( 100 ) 로 정한다. 
3. 탐색 범위가 다시 정해지면 2번과 같이 다시 mid 값과 data값이 같을 때 까지 반복한다!

위의 예시를 Java 코드로 표현 해보자.

int[] ex // 이 객체에 1~100 자연수가 차례대로 들어있다고 생각하자!
int data; // 내가 찾을 데이터

int high = ex.length-1;   // 첫 번째 탐색 범위 중 오른쪽
int low = 0;     // 첫 번째 탐색 범위 중 왼쪽

while(high >= low){
	int mid = (high+low) / 2 ; // 탐색 범위의 가운데 == guess_index 라고 생각해도 괜찮다.
    if( ex[mid] > data )  high = mid -1 ;
    else if ( ex[mid] < data ) low = mid + 1 ;
    else { 
    System.out.println( "index - " + mid + "에서 Find!! " );
    return;
    }
}
System.out.println( data + "를 찾지 못했습니다! ");

이진 탐색은 실행 시간이 빅오표시법으로 O(log n) 이다.

 

 

이진 탐색과 단순 탐색은 정렬이 된 데이터에서만 탐색이 가능하다.

데이터가 많아 질 수록 이진 탐색 > 단순 탐색(효율) 이다!