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

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

Comparison with other Searching

Some problems on Binary Search

• Check if an array is sorted and rotated using Binary Search
• Longest Common Prefix using Binary Search
• Find the Peak Element in a 2D Array/Matrix
• Search an element in a sorted and rotated array with duplicates
• Search for an element in a Mountain Array
• Median of two Sorted Arrays of Different Sizes
• Longest Increasing Subsequence Size (N log N)
• Median of two Sorted Arrays of Different Sizes using Binary Search
• The Painter’s Partition Problem using Binary Search
• Allocate Minimum Number of Pages from N books to M students
• Find largest median of a sub array with length at least K

Variants of Binary Search

Comparison with other Searching

Some problems on Binary Search

• Check if an array is sorted and rotated using Binary Search
• Longest Common Prefix using Binary Search
• Find the Peak Element in a 2D Array/Matrix
• Search an element in a sorted and rotated array with duplicates
• Search for an element in a Mountain Array
• Median of two Sorted Arrays of Different Sizes
• Longest Increasing Subsequence Size (N log N)
• Median of two Sorted Arrays of Different Sizes using Binary Search
• The Painter’s Partition Problem using Binary Search
• Allocate Minimum Number of Pages from N books to M students
• Find largest median of a sub array with length at least K

Источник

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

Easy problems on Searching algorithms

• Find the Missing Number
• Find the first repeating element in an array of integers
• Find the missing and repeating number
• Count 1’s in a sorted binary array
• Two elements whose sum is closest to zero
• Find a pair with the given difference
• Kth smallest element in a row-wise and column-wise sorted 2D array
• Find common elements in three sorted arrays
• Ceiling in a sorted array
• Floor in a Sorted Array
• Find the maximum element in an array which is first increasing and then decreasing
• Given Array of size n and a number k, find all elements that appear more than n/k times

Medium problems on Searching algorithms

• Find all triplets with zero sum
• Find the element before which all the elements are smaller than it, and after which all are greater
• Find the largest pair sum in an unsorted array
• K’th Smallest/Largest Element in Unsorted Array
• Search an element in a sorted and rotated Array
• Find the Minimum element in a Sorted and Rotated Array
• Find a Fixed Point (Value equal to index) in a given array
• Find the k most frequent words from a file
• Find k closest elements to a given value
• Given a sorted array and a number x, find the pair in array whose sum is closest to x
• Find the closest pair from two sorted arrays
• Find three closest elements from given three sorted arrays
• Binary Search for Rational Numbers without using floating point arithmetic

Hard problems on Searching algorithms

Источник

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

We can verify the theoretically derived time complexity with the program BinarySearchRuntime from the GitHub repository. The program generates random arrays with 10,000 to 200,000,000 elements and searches them for a randomly selected element.

Since the times are in the nanosecond range, each measurement consists of searches for 100 different keys. The measurement is repeated 100 times for each array size; then, the median is printed. The following graph shows the average runtime in relation to the array size:

The logarithmic progression can be seen very well.

Binary Search vs. Linear Search

With linear search, the best case is finding the element we are looking for in the first step. In the worst case, we have to search the entire array. In the average case, half of the entries. With n entries, that is n/2 search steps. The duration of the search increases linearly with the number of entries. We say:

The time complexity of the linear search is O(n).

We can measure the runtime of linear search with the LinearSearchRuntime program. The following image shows the comparison of the runtimes of binary and linear search. I had to reduce the range to 100,000 elements to be able to recognize at least a minimal increase of the measured values for the binary search:

We can see the linear time of the linear search very nicely. It is also apparent that the binary search is orders of magnitude faster than the linear search.

Runtime of Binary Search for Small Arrays

Due to the higher complexity of the binary search code, linear search can be faster for small arrays. The following diagram shows a section of the comparison of run times for up to 500 elements. Each measurement point is the median of 100 measurements with 10,000 repetitions each.

That confirms the assumption. For arrays up to a maximum of about 230 elements, linear search is faster than binary search. Of course, this is not a general statement but applies only to my laptop and the JDK I currently use.

You can once again nicely see the linear time – O(n) – compared to the logarithmic time – O(log n).

Runtime of Binary Search in a LinkedList

In the chapter Binary Search in the JDK, I mentioned that the Collections.binarySearch() method can also be applied to a LinkedList . Collections.binarySearch() distinguishes internally between lists that implement the RandomAccess interface, such as ArrayList , and other lists. For lists with «random access», a regular binary search is performed.

To access the middle element in lists without random access, we would have to follow the elements from the beginning to the middle, element by element. From there, we would again reach the center of the left or right half by following the list, element by element. The following diagram should illustrate this:

For example, to find the position of 19, we would first have to follow the orange arrows to the center, then the blue arrows back to 23, and finally the yellow arrow to 19.

That works only with a doubly linked list. For iterating left in a singly linked list, you would have to jump back to the beginning and, from there, follow the arrows to the right again.

No matter if singly or doubly linked – in any case, we have to iterate over more elements than with linear search. While we have an average of n/2 search steps in the linear search in total, we already iterate over n/2 elements to reach the middle in the first step of the binary search. In the second step, we iterate over n/4 elements; in the third step, we iterate over n/8 elements, and so on.

So at first glance, binary search makes absolutely no sense in a LinkedList .

When Is Binary Search in a LinkedList Useful?

Nevertheless, binary search in a LinkedList can be faster than linear search. Although we have to iterate over more elements (as shown in the previous section) – the number of comparisons remains in the order of O(log n)!

Depending on the cost of the comparison function – which can be significantly higher for an object than for a primitive data type – this can make a considerable difference. So if you ever need to search in a LinkedList , it’s worth trying binary search with Collections.binarySearch() and comparing it to linear search.

Summary

This article has shown the principle of binary search and its advantages over linear search for sorted arrays and lists. I demonstrated the theoretically derived time complexity on an example. I also showed that binary search could be useful for a doubly linked list.

A very similar technique is the search in a binary search tree.

If you liked the article, feel free to leave me a comment or share it using one of the share buttons at the end. If you want to be informed when the next articles are published, sign up for my newsletter using the form below.

Источник