Кофе-брейк #156. Как использовать метод Arrays.binarySearch() в Java
Источник: FreeCodeCamp Благодаря этой статье вы узнаете, как использовать метод Arrays.binarySearch() в языке Java.
Что такое Arrays.binarySearch() в языке Java?
- Этот метод ищет в указанном массиве байтов указанное значение, используя алгоритм двоичного поиска.
- Массив должен быть отсортирован (по методу sort(byte[]) ) перед выполнением вызова. Если он не отсортирован, результаты не будут определены.
- Если массив содержит несколько элементов с указанным значением, нет гарантии, какой из них будет найден.
import java.util.Arrays; public class Main < public static void main(String[] args) < char vowels[] = ; char key = 'i'; int foundItemIndex = Arrays.binarySearch(vowels, key); System.out.println("The given vowel is at index: " + foundItemIndex); > > Метод Arrays.binarySearch() принимает массив, который вы хотите найти, в качестве первого аргумента, и ключ, который вы ищете, в качестве второго аргумента. Результатом указанной выше программы будет:
Помните, что метод возвращает индекс найденного элемента, а не сам элемент. Таким образом вы можете сохранить индекс в виде целого числа, подобного тому, который используется в этом примере. По умолчанию метод использует первый индекс массива в качестве начальной точки поиска и длину массива в качестве конечной точки поиска. В этом случае начальный индекс равен 0, а конечный индекс — 6. Вместо того, чтобы использовать начальный и конечный индексы по умолчанию, вы можете определить их самостоятельно. Например, если вы хотите выполнить поиск от индекса 2 к индексу 4, то это можно сделать так:
import java.util.Arrays; public class Main < public static void main(String[] args) < char vowels[] = ; char key = 'i'; int startIndex = 2; int endIndex = 4; int foundItemIndex = Arrays.binarySearch(vowels, startIndex, endIndex, key); System.out.println("The given vowel is at index: " + foundItemIndex); > > В этом случае метод Arrays.binarySearch() принимает массив, который вы хотите найти, в качестве первого аргумента, начальный индекс — в качестве второго аргумента, конечный индекс — в качестве третьего и ключ — в качестве четвертого. Пока вы сохраняете конечный индекс в пределах длины массива, метод должен работать нормально. Но если вы его превысите, то получите исключение Array index out of range . Всё довольно просто, верно? Метод возвращает индекс элемента, если он найден. Но что произойдет, если он не найдет данный элемент?
Что происходит, когда Arrays.binarySearch() не находит данный элемент?
- Метод находит индекс ключа в результатах поиска, если он содержится в массиве в пределах указанного диапазона; иначе получаем (-(insertion point) — 1) .
- Точка вставки определяется как точка, в которой ключ будет вставлен в массив: индекс первого элемента в диапазоне больше, чем ключ, или toIndex (конечный индекс), если все элементы в диапазоне меньше указанного ключа.
- Обратите внимание, что возвращаемое значение будет больше или равно 0 только тогда, когда ключ найден.
package arrays; import java.util.Arrays; public class Main < public static void main(String[] args) < int numbers[] = ; System.out.println(Arrays.binarySearch(numbers, 0)); // -1 > > Давайте снова предположим, что у нас есть массив [5, 6, 7, 8, 9, 10] и ключ поиска 12 , которого явно нет в массиве. В этом случае ключ поиска больше, чем все элементы массива. Здесь insertion point будет таким:
Помните, что если вы не определяете конечный индекс вручную, то метод использует длину массива в качестве конечного индекса, который в данном случае равен 6 . Вы можете реализовать это в фрагменте кода следующим образом:
import java.util.Arrays; public class Main < public static void main(String[] args) < int numbers[] = ; System.out.println(Arrays.binarySearch(numbers, 12)); // -7 > > import java.util.Arrays; public class Main < public static void main(String[] args) < int numbers[] = ; int startIndex = 1; int endIndex = 3; System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 5)); // -2 System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 10)); // -4 > > Попробуйте рассчитать значения самостоятельно. Вы также можете использовать метод Arrays.binarySearch() с такими символами:
import java.util.Arrays; public class Main < public static void main(String[] args) < char vowels[] = ; char key = 'i'; int startIndex = 2; int endIndex = 4; System.out.println(Arrays.binarySearch(vowels, startIndex, endIndex, key)); > > Те же принципы применяются и в том случае, когда заданный ключ поиска не найден. Но при сравнении между символом в массиве и заданным поисковым ключом будет использоваться ASCII-код соответствующего символа. То есть A (65) будет меньше, чем a (97) . Учтите это при перекрестной проверке выходных данных вашей программы.