StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You can use default binary search with custom comparator as your base, and then work our range by your self. I think the right algorithm would be:</p> <ol> <li>Perform binary search on given array. Use comparator which checks <strong>only</strong> for prefix.</li> <li>As result you'll get index of string which starts with your prefix</li> <li>Walk to the left to find first string which matches prefix, remember position.</li> <li>Walk to the right to find first string which matches prefix, remember position.</li> <li>Copy elements from range start to range end from original array. That will be your desired array of all elements with prefix match condition.</li> </ol> <p>Below is implementation in java. It works in happy case scenario but will crash if(I left those checks out to make code look simple):</p> <ul> <li>No strings with given prefix exist in original array</li> <li>There are string with length less then prefix length</li> </ul> <p>Also if you need binary search implementation you could check source of <code>Arrays.binarySearch</code></p> <pre><code>public class PrefixMatch { public static void main(String[] args) { final String[] prefixMathces = prefixMatch(new String[] { "Abc", "Abcd", "Qwerty", "Pre1", "Pre2", "Pre3", "Xyz", "Zzz" }, "pre"); for (int i = 0; i < prefixMathces.length; i++) System.out.println(prefixMathces[i]); } public static String[] prefixMatch(final String[] array, final String prefix) { final Comparator<String> PREFIX_COMPARATOR = new Comparator<String>() { @Override public int compare(String o1, String o2) { return o1.substring(0, prefix.length()).compareToIgnoreCase(o2); } }; final int randomIndex = Arrays.binarySearch(array, prefix, PREFIX_COMPARATOR); int rangeStarts = randomIndex, rangeEnds = randomIndex; while (rangeStarts > -1 && array[rangeStarts].toLowerCase().startsWith(prefix.toLowerCase())) rangeStarts--; while (rangeEnds < array.length && array[rangeEnds].toLowerCase().startsWith(prefix.toLowerCase())) rangeEnds++; return Arrays.copyOfRange(array, rangeStarts + 1, rangeEnds); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload