[알고리즘 구현]Binary Search

Alg 동작 원리

sort가 완료된 자료형 일 때, 전체 배열의 중간값과 비교를 함므로 key가 어느쪽에 있는지 탐색

1. 중간값이다 = 찾았다!
2. 중간값이 key보다 크다 = 왼쪽 탐색
3. 중간값이 key보다 작다 = 오른쪽 탐색

종료 조건은 from이 to보다 더 커질 경우. 왼쪽이든 오른쪽이든 맨 끝으로 가게되면 이 조건을 만족하고 끝이 난다.

시간복잡도(최악의 경우): T(n) = T(n/2)+1 이므로 O(log n)

코드(Java)

public class BinarySearch {

	public static void main(String[] args) {
		int[] data = { 1, 3, 5, 6, 7, 8, 9, 12, 56, 89, 345 };
		binarySearch(data, 89, 0, data.length - 1);
	}

	public static void binarySearch(int[] data, int key, int from, int to) {
		if (from > to) {
			System.out.println("not exist");
			return;
		}
		int mid = Math.abs((from + to) / 2);
		if (data[mid] == key) {
			System.out.println("find :  "+ mid);
		} else if (data[mid] < key) {
			binarySearch(data, key, mid + 1, to);
		} else {
			binarySearch(data, key, from, mid - 1);
		}
	}
}