이진탐색 알고리즘

이진 탐색 (Binary Search)

이진 탐색이란?

이진 탐색 트리는 정렬된 원소 리스트를 입력받아 리스트에 원하는 원소가 있다면 원소의 위치를 반환합니다.

만약 리스트에 원하는 원소가 존재하지 않다면 null을 반환합니다.

! 입력받는 리스트는 반드시 정렬되어 있어야 합니다.

 

 

이진 탐색의 시간 복잡도

 

이진 탐색 구현

이진 탐색은 중간 값을 기준으로 값을 비교하여 점차 탐색 범위를 줄여가는 방식입니다.

탐색 범위를 의미하는 low, high 변수를 선언하고 low, high을 통하여 중간 값을 찾아냅니다.

이 중간 값과 item 값을 비교하여 'item > 중간값'인 경우 low의 위치를 중간 값 인덱스보다 한 칸 뒤에 위치하도록 합니다. 반대로  'item < 중간값'인 경우 high의 위치를 중간 값 인덱스보다 한 칸 앞에 위치하도록 합니다.

 

이 과정을 반복하면서 중간 값과 item 값이 같으면 중간 값 반환 후 탐색을 종료합니다.

만약 'low >= high'상황이 된다면 해당 리스트에는 item 값이 없음을 의미하므로 null을 반환합니다. 

 

 

item < array [mid] 경우

 

item > array[mid] 경우

 

1. 반복문을 이용한 구현

// 반복문을 이용한 구현
private static Object binary_search(int[] array, int item) {
	int low = 0;
	int high = array.length - 1;

	int mid; // 배열의 가운데 index
	int guess; // 배열의 가운데 원소 값 확인

	while (low <= high) {
		mid = (low + high) / 2;
		guess = array[mid];

		if (guess < item) { // 찾는 대상이 찾은 값 보다 큰 경우 (up)
			low = mid + 1;
		} else if (guess > item) { // 찾는 대상이 찾은 값보다 작은 경우 (down)
			high = mid - 1;
		} else { // 값 찾음
			return mid;
		}

	}

	return null;
}

 

2. 재귀 함수를 이용한 구현

// 재귀 함수를 이용한 구현
private static Object binary_search(int[] array, int low, int high, int item) {

	if(low==high) return null;
	
	int mid = (low + high) / 2; // 배열의 가운데 index
	int guess = array[mid]; // 배열의 가운데 원소 값 확인

	if (guess < item) { // 찾는 대상이 찾은 값 보다 큰 경우 (up)
		binary_search(array, mid + 1, high, item);
	} else if (guess > item) { // 찾는 대상이 찾은 값보다 작은 경우 (down)
		binary_search(array, low, mid - 1, item);
	} else { // 값 찾음
		return mid;
	}
	
	return null;
}