Как лучше всего найти число в массиве?

ProgramBox

Как лучше всего найти число в массиве?

Post author:admin
Запись опубликована:6 ноября, 2022
Post category:Вопросы по программированию

#java #search

#java #Поиск

Вопрос:

.. и что, черт возьми, здесь происходит?

     int [] numbers1To9 = new int[]{1,2,3,4,5,6,7,8,9};
    System.out.println("one is here, true or false?: " Arrays.asList(numbers1To9).contains(1));

вывод: здесь один, true или false?: false

1. Arrays.asList() в примитивных массивах возвращает список, единственным элементом которого является сам массив. Это то, что вы получили false. Arrays.asList(numbers1To9).contains(numbers1To9) вернет true .

2. «узнайте что-нибудь сегодня», флажок установлен, спасибо. Если бы вы включили этот лакомый кусочек вместе с простым алгоритмом для достижения того, что я пытаюсь: это было бы заслуженно принято.

3. Лучшая практика поиска в массиве — это перебирать его. Если оно отсортировано, использовать Arrays.binarySearch .

Ответ №1:

При работе с отсортированными массивами или когда операцию сортировки в несортированный массив можно считать «дешевой», binarySearch можно считать хорошим вариантом; Это позволяет избежать создания дополнительных коллекций (таких как Lists ), поскольку оно напрямую работает с исходным массивом, и его механизм направлен на поиск позиции (или один из них), где хранится требуемый ключ. В результате вы можете определить его существование (неявное) и индекс, в котором он находится.

У вас уже есть отсортированный массив, поэтому в вашем случае в этом нет необходимости (что является преимуществом для использования этого алгоритма); Имейте в виду, что при использовании несортированных массивов вызов Arrays.sort перед the binarySearch является обязательным, чтобы избежать «неопределенных» результатов.

Например, если вы хотите узнать 1 , существует ли значение:

     /*Arrays.sort(numbers1To9); -- only if unsorted*/
    boolean found = (Arrays.binarySearch((numbers1To9), 1))>=0?true:false; //--> true

Если вы хотите также получить позицию, например, значения 2 :

     /*Arrays.sort(numbers1To9); -- only if unsorted*/
    int pos = Arrays.binarySearch((numbers1To9), 2); //-->1
    boolean found = pos>=0; //--> true

binarySearch вернет отрицательный результат только в том случае, если элемент не найден. Если найденный ключ дублируется, нет никакой гарантии, какая позиция из указанного ключа вернется.

Независимо от этого, если результат равен >=0 , массив гарантированно будет содержать число, и требуемое значение также гарантированно будет сохранено в возвращаемом индексе.

Результат, когда ключ не найден, как-то интересен

Отрицательный результат, показанный, если ключ не найден, следует этой логике:

(-(точка вставки) — 1). Точка вставки определяется как точка, в которой ключ будет вставлен в массив: индекс первого элемента больше ключа или .length, если все элементы в массиве меньше указанного ключа. Это гарантирует, что возвращаемое значение будет >= 0 тогда и только тогда, когда ключ найден.

Итак, если вы попытаетесь найти любое число больше 9, точка вставки будет numbers1To9.length -> 9 . Следовательно, 10 и INTEGER.MAX_VALUE будет выводить ту же позицию:

 int pos = Arrays.binarySearch((numbers1To9), 10);                // -(9)-1 --> pos=-10
    pos = Arrays.binarySearch((numbers1To9), Integer.MAX_VALUE); // -(9)-1 --> pos=-10

С числом 0 точка вставки будет равна 0 (поскольку 1 больше, а его позиция в массиве равна 0):

 int pos = Arrays.binarySearch((numbers1To9), 0); // -(0)-1 --> pos=-1

Чтобы посмотреть, насколько плохо BinarySearch работает с несортированными массивами:

     int [] numberUnsorted= new int[]{1,2,4,9,7,6,5,8,3};
    int pos = Arrays.binarySearch((numberUnsorted), 3); //--> pos = -3  (FAIL)
        pos = Arrays.binarySearch((numberUnsorted), 9); //--> pos = -10 (FAIL)
        pos = Arrays.binarySearch((numberUnsorted), 6); //--> pos = -4  (FAIL)

Поэтому называть их «неопределенными» — это действительно доброжелательный подход

Обратите внимание, что BinarySearch будет «одной из лучших практик» для поиска
числа в массиве с условием сортировки массива. В других сценариях, когда массив не отсортирован, вы можете знать о сложности его сортировки и решить, будет ли лучшим подходом другой механизм, который не требует операции сортировки. Это будет зависеть от типа, размера и значений массива. Обычно не существует «наилучших способов определения» без знания конкретного контекста поиска

Ответ №2:

Лучший способ найти число в массиве Зависит от вашего массива, отсортирован он или нет

Если ваш массив отсортирован, вы сможете найти число в массиве за время O(log (N)).

Но если ваш массив не отсортирован, вам нужно будет рассмотреть возможность сортировки массива, и после того, как существует несколько алгоритмов, вы сможете найти свой номер в массиве.

Например, двоичный поиск и многое другое…

1. Не O(1), O(log(N)). И это при бинарном поиске. Для несортированного массива не существует «нескольких алгоритмов». Есть один: исчерпывающий поиск.

2. Двоичный поиск требует сортировки массива.

Ответ №3:

В качестве альтернативы поиску числа в int[] самостоятельно и близкому к вашей собственной попытке, вы можете довольно легко преобразовать int[] в список:

 int [] numbers1To9 = new int[]{1,2,3,4,5,6,7,8,9};
List<Integer> ilist = IntStream.of(numbers1To9).boxed().collect(Collectors.toList());
System.out.println("one is here, true or false?: "  ilist.contains(1));

Вывод:
one is here, true or false?: true

Редактировать

Как упоминалось в комментарии ниже, если ваша единственная цель — проверить наличие значения, вам вообще не нужно вставлять и собирать:

 boolean contains1 = IntStream.of(numbers1To9).anyMatch(i -> i == 1);
System.out.println("one is here, true or false?: "  contains1);