[JAVA] 이진 탐색 (Binary Search)

크기가 n인 오름차순으로 정렬된 배열 A에 대한 탐색

 

1. x가 배열의 중간 요소와 같으면 찾았으니 끝낸다.
2. x가 배열의 중간 요소보다 작으면 앞쪽에 위치한 배열 반쪽에서 같은 방법으로 x를 찾는다.
3. x가 배열의 중간 요소보다 크면 뒤쪽에 위치한 배열 반쪽에서 같은 방법으로 x를 찾는다.

 

시간복잡도 O(logN)

 

알고리즘

BinarySearch(A[], first, last, x)

if (first > last) return -1
else {
	mid = (first + last) / 2
    if (x = A[mid]) return mid
    else if (x < A[mid]) return BinarySearch(A, first, mid - 1, x)
    else return BinarySearch(A, mid + 1, last, x)
}

 

JAVA

public class BinarySearch {
	public static void main(String[] args) {
		int[] A = {10, 12, 13, 14, 18, 20, 
				25, 27, 30, 35, 40, 45, 47};
		int x = 18;
		int n = A.length;
		int location = binarySearch(A, 0, n - 1, x);
		
		System.out.println(x + "의 지수 = " + location);
	}
	
	public static int binarySearch(int[] A, int first, int last, int target) {
		int result;
		if (first > last) return -1;
		else {
			int mid = (first + last) / 2;
			if (target == A[mid]) result = mid;
			else if (target < A[mid]) {
				result = binarySearch(A, first, mid - 1, target);
			}
			else {
				result = binarySearch(A, mid + 1, last, target);
			}
		}
		
		return result;
	}
}