Бинарный метод поиск java

Бинарный поиск на Java

С одной стороны, для подобных алгоритмов используют уже готовые функции стандартной библиотеки, с другой – подобные вопросы на собеседованиях позволяют узнать полезное о кандидате.

Первое что приходи на ум: перебор элементов в массиве до нужного, тогда если количество элементов равно n и нужный нам элемент будет последним, нам потребуется сделать n проверок элементов до нахождения нужного, про такой случай и говорят что сложность алгоритма равна O(n).

Рассмотрим другой подход — бинарный поиск – возьмем средний элемент отсортированного массива и сравним его c искомым. Если элемент меньше – продолжим поиск в левой части массива, если больше в правой, пока не останется нужный элемент. Таким образом нам понадобится число операций равное тому, сколько раз нам нужно поделить массив размером n пополам.

Например, для массива в 16 элементов мы сначала поделим его на два по 8, потом 8 на два по 4, потом 4 на два по 2 и на конец 2 пополам, те всего 4 операции в худшем случае. Такое число равно двоичному логарифму.

Без рекурсии

public class Binary < public static void main(String[] args) < int[] values = ; int valueToFind = 3; System.out.printf("Index = %d%n", binarySearch(values, valueToFind, 0, values.length - 1)); > private static int binarySearch(int[] sortedArray, int valueToFind, int low, int high) < int index = -1; while (low else if (sortedArray[mid] > valueToFind) < high = mid - 1; >else if (sortedArray[mid] == valueToFind) < index = mid; break; >> return index; > >

С использованием рекурсии

public class Binary < public static void main(String[] args) < int[] values = ; int valueToFind = 3; System.out.printf("Index = %d%n", binarySearch(values, valueToFind, 0, values.length - 1)); > private static int binarySearch(int[] values, int valueToFind, int l, int r) < if (l == r) < return (values[l] == valueToFind) ? l : -1; >int m = l + (r - l) / 2; if (valueToFind > values[m]) < return binarySearch(values, valueToFind, m + 1, r); >else if (values[m] > valueToFind) < return binarySearch(values, valueToFind, l, m - 1); >return m; > >

Если элемент не найден, то вернется -1 .

Во многих примерах в интернете можно встретить запись int m = (l + r) / 2; , вместо int mid = l + (r — l) / 2; . И у меня в заметке тоже была такая запись, пока один из читателей не обратил на это внимание.

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

Например, если l = 2147483647 и r = 2147483647 , сумма l и r будет равна 4294967294, что превышает максимальное значение, которое может удерживать int , вызывая переполнение.

С другой стороны, если вы используете mid = l + (r — l) / 2; это будет работать, как и ожидалось, потому что вычитание будет сделано первым, а результат будет равен нулю, поэтому деление будет равно нулю, а сложение вернет значение l .

Источник

Кофе-брейк #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) . Учтите это при перекрестной проверке выходных данных вашей программы.

Источник

Бинарный поиск

Представьте, что у вас есть список отсортированных по алфавиту диснеевских героев, и вам нужно найти Микки Мауса.

Линейно это было бы долго. А если воспользоваться «методом разрывания справочника пополам», мы попадаем сразу на Jasmine, и можем смело отбросить первую половину списка, понимая, что Mickey там не может быть.

По этому же принципу отбрасываем второй столбец. Продолжая такую стратегию, мы найдем Микки буквально за пару шагов.

Давайте найдем число 144 . Делим список пополам, и попадаем на число 13 . Оцениваем, больше или меньше искомое число, чем 13 .

13 , так что мы можем игнорировать всё, что находится левее 13 и само это число. Теперь наш список поиска выглядит так:

Тут чётное число элементов, поэтому выбираем принцип, по которому выбираем «среднее» (ближе к началу или концу). Допустим, мы избрали стратегию близости к началу. В таком случае, наша «середина» = 55 .

55 . Мы снова отбрасываем левую половину списка. К счастью для нас, следующее среднее число и будет 144 .

Мы нашли 144 в массиве из 13 элементов с помощью бинарного поиска всего за три шага. Линейный поиск в такой же ситуации справился бы аж за 12 шагов. Поскольку этот алгоритм на каждом шаге уменьшает количество элементов в массиве вдвое, он найдет искомое за асимптотическое время О(log n) , где n – количество элементов в списке. То есть, в нашем случае асимптотическое время = O(log 13) (это чуть больше трёх).

Псевдокод функции бинарного поиска:

binarySearch(key, array[], min, max): if (max < min): return -1 else: midpoint = findMidPoint(min, max) if (array[midpoint] < key): binarySearch(key, array, midpoint + 1, max) else if (array[midpoint] >key): binarySearch(key, array, min, midpoint - 1) else: return midpoint

Функция принимает на вход 4 аргумента: искомое key , массив данных array[] , в котором находится искомое, min и max — указатели на максимальное и минимальное число в массиве, на которое мы смотрим на данном шаге алгоритма.

Для нашего примера изначально дана такая картинка:

Разберем код далее. midpoint — наша середина массива. Она зависит от крайних точек и находится по центру между ними. После того, как мы нашли середину, проверяем, меньше ли она нашего числа key .

midpoint = findMidPoint(min, max) if (array[midpoint] < key): binarySearch(key, array, midpoint + 1, max)

Если это так, то key также больше, чем любое из чисел левее середины, и мы можем вызвать бинарную функцию снова, только теперь наш min = midpoint + 1 . Если окажется, что key , мы можем отбросить само это число и все числа, лежащие справа от него. И мы вызываем бинарный поиск по массиву от числа min и вплоть до значения (midpoint – 1) .

else if (array[midpoint] > key): binarySearch(key, array, min, midpoint - 1)

Третья ветка: если значение в midpoint не больше и не меньше, чем key, ему ничего не остается, как быть искомым числом. Его мы и возвращаем в таком случае и заканчиваем работу программы.

Наконец, может статься так, что искомое число и вовсе отсутствует в массиве. Для учёта этого случая делаем такую проверку:

И возвращаем (-1) , чтобы указать, что мы ничего не нашли.

Источник