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

이분탐색이란?

정렬된 배열 또는 리스트에서 특정 값을 찾는 고속 탐색 방법.
이진 탐색은 탐색범위를 1/2로 줄이며 탐색하기에,  선형탐색에 비해 빠르다.

BUT 배열, 리스트는 정열되어 있어야 한다는 전제조건

 

1. 배열의 '중간 값'을 선택 후 찾는값과 비교.
2. 중간값이 찾는값보다 크면 '배열의 왼쪽 부분'에서 탐색 시작.
   중간값이 찾는값보다 작으면 '배열의 오른쪽 부분'에서 탐색 시작.
3. 위 과정 반복
   
   

시간복잡도 비교

순차적 탐색은 최악의 경우 배열의 끝까지 탐색하지만, 이분탐색은 1/2씩 범위를 줄여서 탐색하므로 빠르다.

방식	시간복잡도
순차적 탐색	O(n)
이분 탐	O(logn)

 

 

 

자바 구현

- 반복문으로 구현 

public static boolean BSearch(int[] arr, int n) {
		int left = 0;
		int right = arr.length - 1;
		int mid;

		while (left <= right) {
			mid = (left + right) / 2;
			if (arr[mid] < n) left = mid + 1;
			else if (arr[mid] > n) right = mid - 1;
			else return true;
		}
		return false;
	}

- 재귀로 구현

 

public static boolean BSearchRecursive(int[] arr, int n, int left, int right) {
		if(left > right) return false;
		
		int mid = (left + right) / 2;
        
		if (arr[mid] < n) 
        	return BSearchRecursive(arr, n, mid +1, right);
		else if (arr[mid] > n) 
        	return BSearchRecursive(arr, n, left, mid - 1);
		else 
        	return true;
		
	}

 

• 참고 https://adjh54.tistory.com/187#google_vignette