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

원리

정렬된 데이터 배열에서 특정한 값을 찾아내는 알고리즘
1. 배열의 중간의 임의의 값을 선택해서 찾으려는 값과 비교
2-1. 만약 중간값보다 작으면 최대값을 중간값-1 로 설정
2-2. 만약 중간값보다 크면 최소값을 중간값+1 로 설정
시간 복잡도 : O(logN)

구현

private static int binarySearch(int[] A, int n) {
	int first = 0;
	int last = A.length - 1;
	int mid = 0;

	while (first <= last) {
		mid = (first + last) / 2;

		if (n == A[mid])
			return 1;
		else {
			if (n < A[mid])
				last = mid - 1;
			else
				first = mid + 1;
		}
    	}
	return 0;
    }