CODEWITHSUNDEEP
javaalgorithmsearchbinary-search
ipman
ipman

Reputation: 1222

Finding the first element that starts with a specified String in a sorted String array in Java

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?

Upvotes: 3

Views: 793

Answers (1)

amit
amit

Reputation: 178481

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:

  1. 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.
  2. 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]);

Upvotes: 6

Related Questions