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

Java Guides

In computer science, searching is the process of finding an item with specified properties from a collection of items. The items may be stored as records in a database, simple data elements in arrays, text in files, nodes in trees, vertices and edges in graphs, or they may be elements of other search spaces.

Why do we need Searching?

Searching is one of the core computer science algorithms. We know that today’s computers store a lot of information. To retrieve this information proficiently we need very efficient search algorithms.

There are certain ways of organizing the data that improve the searching process. That means, if we keep the data in proper order, it is easy to search for the required element. Sorting is one of the techniques for making the elements ordered. In this article, we will see different search algorithms.

Binary Search with Example

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

Let us consider the problem of searching for a word in a dictionary. Typically, we directly go to some approximate page [say, middle page] and start searching from that point. If the name that we are searching for is the same then the search is complete. If the page is before the selected pages then apply the same process for the first half; otherwise, apply the same process to the second half. Binary search also works in the same way. The algorithm applying such a strategy is referred to as a binary search algorithm.

How Binary Search Works?

For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of binary search with a pictorial example.

The following is our sorted array and let us assume that we need to search the location of value 10 using binary search.

Now we compare the value stored at location 4, with the value being searched, i.e. 10. We find that the value at location 4 is 8, which is not a match. As the value is greater than 8 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.

low = mid + 1 mid = low + (high - low) / 2 

The value stored at location 7 is not a match, rather it is more than what we are looking for. So, the value must be in the lower part from this location.

Binary Search Implementation using Java

Let’s write a source code for binary search in Java. There are many ways we can write logic for binary search:

1. Iterative implementation
2. Recursive Implementation
3. Using Arrays.binarySearch()
4. Using Collections.binarySearch()

Iterative Implementation

public class BinarySearch < public int binarySearchIteratively(int[] sortedArray, int key) < int low = 0; int high = sortedArray.length - 1; int index = Integer.MAX_VALUE; while (low  high) < int mid = (low + high) / 2; if (sortedArray[mid]  key) < low = mid + 1; > else if (sortedArray[mid] > key) < high = mid - 1; > else if (sortedArray[mid] == key) < index = mid; break; > > return index; > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index = binSearch.binarySearchIteratively(sortedArray, key); System.out.println("Search element found " + key+ " in location index : " + index); > >

Search element 6 found in location index : 7 

The binarySearchIteratively method takes a sortedArray, key & the low & high indexes of the sortedArray as arguments. When the method runs for the first time the low, the first index of the sortedArray, is 0, while the high, the last index of the sortedArray, is equal to its length – 1.

The middle is the middle index of the sortedArray. Now the algorithm runs a while loop comparing the key with the array value of the middle index of the sortedArray.

Recursive Implementation

public class BinarySearch < public int binarySearchRecursively(int[] sortedArray, int key, int low, int high) < int middle = (low + high) / 2; if (high  low) < return -1; > if (key == sortedArray[middle]) < return middle; > else if (key  sortedArray[middle]) < return binarySearchRecursively(sortedArray, key, low, middle - 1); > else < return binarySearchRecursively(sortedArray, key, middle + 1, high); > > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index = binSearch.binarySearchRecursively(sortedArray, key, 0, sortedArray.length -1); System.out.println("Search element found in location index : " + index); > >

Search element found in location index : 7 

The binarySearchRecursively method accepts a sortedArray, key, the low and high indexes of the sortedArray.

Using Arrays.binarySearch()

public class BinarySearch < public int runBinarySearchUsingJavaArrays(int[] sortedArray, Integer key) < int index = Arrays.binarySearch(sortedArray, key); return index; > public static void main(String[] args) < int[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binSearch = new BinarySearch(); int index1 = binSearch.runBinarySearchUsingJavaArrays(sortedArray, key); System.out.println("Search element found in location index : " + index1); > >

Search element found in location index : 7

Using Collections.binarySearch()

public class BinarySearch < public int runBinarySearchUsingJavaCollections(ListInteger> sortedList, Integer key) < int index = Collections.binarySearch(sortedList, key); return index; > public static void main(String[] args) < Integer[] sortedArray = < 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 >; int key = 6; BinarySearch binarySearch = new BinarySearch(); int index1 = binarySearch.runBinarySearchUsingJavaCollections(Arrays.asList(sortedArray), key); System.out.println("Search element found in location index : " + index1); > >

Search element found in location index : 7 

Auxiliary Space: O(1) in the case of iterative implementation. In the case of recursive implementation, O(Logn) recursion call stack space.

Источник

Бинарный поиск на 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 .

Источник

Алгоритм двоичного поиска в Java

В этой статье мы рассмотрим преимущества двоичного поиска по сравнению с простым линейным поиском и рассмотрим его реализацию на Java.

2. Необходимость эффективного поиска

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

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

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

Затем он возвращает элементы, цена которых меньше или равна предельной цене. Этот линейный поиск имеет временную сложностьO(n).

Это означает, что чем больше бутылок вина в нашей системе, тем больше времени это займет. The search time increases proportionately to the number of new items introduced.с

Если мы начнем сохранять элементы в отсортированном порядке и искать элементы с помощью двоичного поиска, мы можем достичь сложностиO(log n).

При двоичном поиске время, затрачиваемое на результаты поиска, естественным образом увеличивается с размером набора данных, но не пропорционально.

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

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

Помните — ключевым аспектом здесь является то, что массив уже отсортирован.

Если поиск заканчивается, а оставшаяся половина остается пустой,key отсутствует в массиве.

3.1. Итеративный импл

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) < int index = Integer.MAX_VALUE; while (low else if (sortedArray[mid] > key) < high = mid - 1; >else if (sortedArray[mid] == key) < index = mid; break; >> return index; >

МетодrunBinarySearchIteratively принимает в качестве аргументов индексыsortedArray,key иlow &highsortedArray. Когда метод запускается в первый раз,low, первый индексsortedArray, равен 0, аhigh, последний индексsortedArray, равен его длина — 1.

middle — средний индексsortedArray. Теперь алгоритм запускает циклwhile, сравниваяkey со значением массива среднего индексаsortedArray.

3.2. Рекурсивный Impl

Теперь давайте посмотрим на простую рекурсивную реализацию:

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) < int middle = (low + high) / 2; if (high < low) < return -1; >if (key == sortedArray[middle]) < return middle; >else if (key < sortedArray[middle]) < return runBinarySearchRecursively( sortedArray, key, low, middle - 1); >else < return runBinarySearchRecursively( sortedArray, key, middle + 1, high); >>

МетодrunBinarySearchRecursively принимаетsortedArray,key,, индексыlow иhigh дляsortedArray.

3.3. ИспользуяArrays.binarySearch()

int index = Arrays.binarySearch(sortedArray, key);

A sortedArray иintkey, который должен быть найден в массиве целых чисел, передаются в качестве аргументов методуbinarySearch классаArrays Java. .

3.4. ИспользуяCollections.binarySearch()

int index = Collections.binarySearch(sortedList, key);

A sortedList иIntegerkey, который должен быть найден в списке объектовInteger, передаются в качестве аргументов методуbinarySearch JavaCollections класс.

3.5. Спектакль

Whether to use a recursive or an iterative approach for writing the algorithm is mostly a matter of personal preference. Но все же вот несколько моментов, о которых следует помнить:

1. Рекурсия может быть медленнее из-за накладных расходов на поддержаниеstack и обычно занимает больше памяти 2. Рекурсия не удобна дляstack-. Это может вызватьStackOverflowException при обработке больших наборов данных 3. Рекурсия вносит ясность в код, поскольку делает его короче по сравнению с итеративным подходом

В идеале, бинарный поиск будет выполнять меньшее количество сравнений в отличие от линейного поиска для больших значений n. Для меньших значений n линейный поиск может работать лучше, чем двоичный поиск.

Следует знать, что этот анализ является теоретическим и может варьироваться в зависимости от контекста.

Такжеthe binary search algorithm needs a sorted data set which has its costs too. Если мы используем алгоритм сортировки слиянием для сортировки данных, к нашему коду добавляется дополнительная сложностьn log n.

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

4. Заключение

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

Пожалуйста, найдите код для руководстваover on GitHub.

Источник