import java.util.Arrays;
public class ArrayUtil {
public static int findClosestNumberInArray(int[] numbers, int number) {
if (numbers.length == 0) {
throw new IllegalArgumentException("Empty array");
} else if (numbers.length == 1) {
return numbers[1];
} else if (numbers.length == 2) {
return shouldFindNumbersFromLeftToRight(numbers, number) ?
numbers[0] : numbers[1];
}
int[] sortedNumbers = new int[numbers.length];
System.arraycopy(numbers, 0, sortedNumbers, 0, numbers.length);
Arrays.sort(sortedNumbers);
return shouldFindNumbersFromLeftToRight(sortedNumbers, number) ?
findClosestNumberFromLeftToRight(sortedNumbers, number) :
findClosestNumberFromRightToLeft(sortedNumbers, number);
}
private static boolean shouldFindNumbersFromLeftToRight(int[] sortedNumbers, int number) {
if (sortedNumbers.length <= 3) {
return getNumbersMatchLevel(sortedNumbers[0], number) <
getNumbersMatchLevel(sortedNumbers[sortedNumbers.length - 1], number);
}
int middleIndex = sortedNumbers.length >> 1;
return getNumbersMatchLevel(sortedNumbers[middleIndex],number) <
getNumbersMatchLevel(sortedNumbers[middleIndex + 1], number);
}
private static int findClosestNumberFromLeftToRight(int[] sortedNumbers, int number) {
int currentIndex = 0;
int currentClosestMatchLevel = Integer.MAX_VALUE;
for (int i = currentIndex; i < sortedNumbers.length; i++) {
int matchLevel = getNumbersMatchLevel(sortedNumbers[i], number);
if (matchLevel == 0) {
return sortedNumbers[i];
} else if (matchLevel < currentClosestMatchLevel) {
currentIndex = i;
currentClosestMatchLevel = matchLevel;
} else if (matchLevel > currentClosestMatchLevel) {
break;
}
}
return sortedNumbers[currentIndex];
}
private static int findClosestNumberFromRightToLeft(int[] sortedNumbers, int number) {
int currentIndex = sortedNumbers.length - 1;
int currentClosestMatchLevel = Integer.MAX_VALUE;
for (int i = currentIndex; i > 0; i--) {
int matchLevel = getNumbersMatchLevel(sortedNumbers[i], number);
if (matchLevel == 0) {
return sortedNumbers[i];
} else if (matchLevel < currentClosestMatchLevel) {
currentIndex = i;
currentClosestMatchLevel = matchLevel;
} else if (matchLevel > currentClosestMatchLevel) {
break;
}
}
return sortedNumbers[currentIndex];
}
private static int getNumbersMatchLevel(int number1, int number2) {
return Math.abs(number1 - number2);
}
public static void main(String[] args) {
int[] numbers = {1, 100, -2, 0, 11, 5, 7, 102, 177, - 1000, 5000, 200, 15, 16, -1, -100, -1000, -150, -333};
System.out.println(findClosestNumberInArray(numbers, 101));
System.out.println(findClosestNumberInArray(numbers, 1));
System.out.println(findClosestNumberInArray(numbers, -500));
}
}