이진 검색(타겟보다 작은 숫자 찾기)

class Solution {
	/**
	 * target 혹은 target보다 작은 수의 인덱스를 리턴.
	 * 
	 * @param arr    : 정렬되어 있는 상태의 배열
	 * @param target : 검색할 수
	 * @return 타겟과 같은 수의 인덱스 혹은 타켓보다 작은 수의 인덱스.
	 **/
	public int binarySearch(int[] arr, int target) {
		int start = 0;
		int end = arr.length - 1;
		// target보다 작은 수가 없을 떄는 -1를 리턴함으로써 없음을 알림.
		if (arr[start] > target) {
			return -1;
		}
		// 가장 큰 수보다 target이 클 경우 가장 뒤에 인덱스를 리턴.
		if (arr[end] < target) {
			return end;
		}

		while (start < end) {
			int mid = (start + end) / 2;
			if (arr[mid] <= target) {
				start = mid+1;
			} else {
				end = mid;
			}
		}
		return end-1;
	}
}