[JAVA] 이진탐색(Binary Search)

이진탐색

 이진 탐색(binary search)는 정렬되어 있는 자료들의 집합에서 특정 자료를 찾고자 할 때 많이 사용되며 매우 빠른 탐색 알고리즘이다. 이진 탐색은 '퀵정렬'과 유사하게 '분할 후 정복(divide and conquer)'의 전략을 사용한다. 이 전략을 사용하는 알고리즘은 문제를 나누어 해결해 나가는 방법이기 때문에 실행시간은 log의 설징을 갖는다. 특히 문제의 크기를 정확히 양분하는 경우에는 최악의 경우라고 logN의 성능을 보장한다.

 이진 탐색의 탐색 시간은 'T = K * logN'으로 O(logN)이다. 선형 탐색의 시간보다 상당히 빠르지만 이진 탐색은 반드시 정렬이 되어있어야 한다. 그러므로 정렬되지 않는 리스트의 경우에는 정렬하는 비용 또한 상당히 들 것이다. 이와 같은 단점에도 불구하고 다음과 같은 상황에서 이진 탐색은 효율적인 성능을 제공한다.

 1) 새로운 자료가 추가되었어도 모든 자료가 재정렬이 일어나지 않는 경우 -> 해싱, 인덱스를 이용하는 경우

 2) 획기적으로 빠르고, 효율적인 자료의 재정렬이 가능한 자료 구조를 사용할 경우 -> B-트리 계열의 트리 구조 사용

다음은 이진 탐색의 JAVA 소스이다.

package Search;

public class BinarySearch {
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

		binarySearch(2, arr);
	}

	public static void binarySearch(int iKey, int arr[]) {
		int mid;
		int left = 0;
		int right = arr.length - 1;

		while (right >= left) {
			mid = (right + left) / 2;

			if (iKey == arr[mid]) {
				System.out.println(iKey + " is in the array with index value: " + mid);
				break;
			}

			if (iKey < arr[mid]) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}

		}
	}
}

+

기술면접에서 이진탐색을 왜 구현하지 못했을까... 자료구조 시간에 그렇게 공부하고 이해하고 구현하고 다 해본 것을ㅠㅠ

기본을 먼저 보고 갔어야 하는 건데, 괜히 다른 알고리즘을 너무 보고 갔더니 간단한 알고리즘조차 어렵게만 생각하고 복잡하게 풀려고 한 것 같다.. 그래서 다시 기본기를 훑어보고자 이렇게 블로그에 남겨놓는다.