[알고리즘] 이분/이진 탐색 ( Binary Search )

 

◇  설명

  :  정렬된 데이터 집합을 이분화하면서 탐색하는 방법

  ①  오름차순으로 배열 정렬
  ②  중간 값( 평균 값 )부터 찾음 ( 찾으려는 값과 비교 ) 
  ③  찾으려는 값이 중간값보다 크면 아래로 내려가고, 작으면 위로 올라감

  -  시간복잡도가 일반 순차 탐색보다 훨씬 빠름 
   ┌  전체 탐색 : O(N)
   └  이분 탐색 : O(logN)

 

◇  코드

  ex)  정렬된 배열에서 찾고자 하는 값의 인덱스 구하기

	// 재귀
	public static int binary_search_idx( int a[], int value, int low, int high ) {  
		if( high <= low )
			return -1;
		int mid = ( low + high ) / 2;
		if( a[mid] > value )
			return binary_search_idx( a, value, low, mid - 1 );
		else if( a[mid] < value )
			return binary_search_idx( a, value, mid + 1, high );
		else
			return mid;
	}
    
	// 반복문
	public static int binary_search_idx( int a[], int value ) {			    
		int low = 0, high = a.length - 1, mid;
		while( low <= high ) {
			mid = ( low + high ) / 2;
			if( a[mid] > value )
				high = mid - 1;
			else if( a[mid] < value )
				low = mid + 1;
			else
				return mid;
		}
		return -1;
	}

// 	low, 	left, 	start
// 	high, 	right, 	end

  ex)  lower bound, upper bound 구하기

	public int lower_bound( int k, int a[] ) {	
		// 배열 a에서 k값이 처음으로 나타나는 인덱스
		int start = 0, end = a.length - 1, mid;
		while( start < end ) {
			mid = (start + end) / 2;
			if( a[mid] >= k )		
				end = mid;
			else start = mid + 1;
		}
		return end;
	}
	
	public int upper_bound( int k, int a[] ) {	
		// 배열 a에서 k보다 큰 값이 처음으로 나타나는 인덱스
		int start = 0, end = a.length - 1, mid;
		while( start < end ) {
			mid = (start + end) / 2;
			if( a[mid] > k )	
				end = mid;
			else start = mid + 1;
		}
		return end;
	}