Menu
I need to find all elements in sorted array with Arrays.binarySearch method. I want to iterate binary search in lowerbound = pos + 1 (pos is previous match), but binarySearch is not guaranteed to return first match (min match index)?
How can I make this?
291
A binary search only gives you the position of the value you want, or the position of 1 of them if duplicated. To display all duplicates and indexes, you need to do a secondary search around the position returned by binary search routine.
Binary search works for integer arrays, but not for double arrays.
Simply put, the Arrays. binarySearch() method can look for a given element in a sorted array and return its index if found. Remember, the method returns the index of the found item and not the item itself.
Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search.
You can easily use the result of binarySearch to get all the matches :
long[] sortedArr = ...
int index = Arrays.binarySearch (sortedArr, value);
int first = index;
int last = index;
if (index >= 0) {
while (first > 0 && sortedArr[first-1] == value)
first--;
while (last < sortedArr.length - 1 && sortedArr[last+1] == value)
last++;
}
After you run this code, the indices between first and last (inclusive) are all the indices that contain the searched value.
55
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
