I have a sorted String array in Java. I am trying to find the first element which starts with a user specified String in that array. I thought binary search at first, but it finds the equal String not the one which starts with the user specified String. How should I modify the binary search so that I can achieve what I want to do?
2
-
Yes, that search could/should be binary. Show us your code, searching for "ranges" is a bit complicated sometimesBergi– Bergi2012-10-21 11:42:05 +00:00Commented Oct 21, 2012 at 11:42
-
I am using Arrays.binarySearch() method in standard library.ipman– ipman2012-10-21 11:45:58 +00:00Commented Oct 21, 2012 at 11:45
Add a comment
|
1 Answer
Binary search can find you the "last element which is smaller then the desired element" if the element does not exist (sometimes refered as "The index where you should insert it").
By doing binary search with this functionality you can find an element and check:
- If it is the exact element - then it is the first element in the array with this prefix, since it is the "smallest" element with this prefix, and you are done.
- If it is not the same element - by increasing one - you get the "smallest element which is bigger then the desired element". This element is the first element in the array with this prefix (if the array has one).
This functionality is very common - for example it exists in java's Arrays.binarySearch(). From the javadocs:
Returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key
From the index just found, it is easy to find the desired element.
Code snap:
String[] arr = { "aa" , "bb","c", "cc" , "ccc", "cccc", "ddD" };
int idx = Arrays.binarySearch(arr, "c");
if (idx < 0)
System.out.println(arr[-1 * idx - 1]);
else System.out.println(arr[idx]);
