#java #arrays #binary-search
Вопрос:
Я новичок в Java и пытаюсь сделать следующее:
Учитывая массив целых чисел, если целое число в массиве находится между 70 и 79, выведите «Да». В противном случае выведите «нет».
Вот мой код до сих пор:
import java.util.Arrays;
int temperatures[] = {45, 70, 71, 67}; //create array
Arrays.sort(temperatures); //sort temperatures
int key = 70; //define key to be searched
int result = Arrays.binarySearch(temperatures,key);
Я знаю, что это поможет мне найти значение 70, которое находится в массиве температур, но как лучше всего использовать BinarySearch, чтобы узнать, есть ли в массиве какое-либо значение 70-х годов?
Ответ №1:
Мы можем использовать тот факт, что Arrays.binarySearch возвращается -(insertion point) - 1 , если элемент не найден. Мы можем найти 70 с помощью binarySearch . Если он будет найден, отлично! В противном случае посмотрите на точку вставки. Если он находится вне диапазона, то каждый элемент меньше 70. В противном случае точкой вставки будет самый маленький элемент в массиве, размер которого превышает 70. Если это больше или равно 80, мы знаем, что в массиве нет чисел в диапазоне 70-79.
Если вы просто инвертируете каждое условие в приведенном выше объяснении, вы получите:
int result = Arrays.binarySearch(temperatures, 70);
if (result >= 0 || // we found 70, or
(-result - 1 < temperatures.length amp;amp; // insertion point in range, and
temperatures[-result - 1] < 80) // insertion point less than 80
) {
System.out.println("There is at least one temperature in the array that is within the range 70-79");
}
Ответ №2:
Установите логическое значение false, выполните итерацию по массиву, начиная с первого элемента, проверьте каждый элемент, пока логическое значение равно false, а индекс меньше длины массива. Если элемент находится в диапазоне от 70 до 79, установите логическое значение true. Проверьте логическое значение и выведите «да», если логическое значение истинно.
Комментарии:
1. Хотя это дает правильный ответ, он не использует преимущества сортировки массива и поэтому занимает O(n) времени вместо O(log n).
2. Это похоже на вопрос для курса CS101, поэтому я дал на него ответ.
3. В вашем ответе нет ничего плохого, но я думаю, что на эту деталь стоит обратить внимание.
4. Я согласен с тем, что вы сказали (если массив отсортирован). Я хотел объяснить, почему я дал такой ответ (и почему это был всего лишь алгоритмический ответ). Первая часть вопроса, похоже, касается несортированного массива. Затем человек, задающий вопрос, предлагает отсортировать массив. И сортировка массива, вероятно, включает алгоритм nlog(n) (алгоритм, используемый массивами Java.сортировка-это nlog(n)?). Кроме того, если вопрос касается курса CS, мой ответ-это то, что, вероятно, искал бы профессор.
Ответ №3:
binarySearch позволяет указать a Comparator , который определяет, какой элемент больше и когда они равны.
Если мы используем компаратор, который сравнивает числа, деленные на 10, то мы можем использовать binarySearch .
import java.util.Arrays;
import java.util.Comparator;
public class SO69217093 {
public static void main(String[] args) {
Comparator<Integer> comparator = new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
int decade1 = o1 / 10;
int decade2 = o2 / 10;
return Integer.compare(decade1, decade2);
}
};
Integer temperatures[] = {45, 70, 71, 67}; //create array
Arrays.sort(temperatures); //sort temperatures
int key = 70; //define key to be searched
int result = Arrays.binarySearch(temperatures,70, comparator);
int result2 = Arrays.binarySearch(temperatures,80, comparator);
}
}
Поскольку Comparator работает с объектами, а не с примитивами, вам нужно будет использовать массив Integer .