Created
December 25, 2012 18:05
-
-
Save Bekt/4374513 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//http://coolcodebro.blogspot.com/2012/12/find-string-in-array-interspersed-with.html | |
//Average case: O(log(n)), Worst case: O(n/2) => O(n) | |
void run() { | |
String[] strings = {"at", "", "", "", "ball", "byd", "", "car", "", "", "dad", "", ""}; | |
String strToFind = "byd"; | |
System.out.printf("IndexOf \"%s\": %d%n", strToFind, search(strings, strToFind)); | |
} | |
int search(String[] strings, String find) { | |
if(strings == null || strings.length == 0 || find == null || find.length() == 0) | |
return -1; | |
return searchRec(strings, find, 0, strings.length-1); | |
} | |
int searchRec(String[] strings, String find, int low, int high) { | |
if(low > high) | |
return -1; | |
int mid = (low + high) / 2; | |
//Find the next non-empty string | |
if(strings[mid].isEmpty()) { | |
int lo = mid; | |
int hi = mid; | |
while(true) { | |
if(lo-- < low || hi++ > high) | |
return -1; | |
if(lo >= low && !strings[lo].isEmpty()) { | |
mid = lo; | |
break; | |
} | |
if(hi <= high && !strings[hi].isEmpty()) { | |
mid = hi; | |
break; | |
} | |
} | |
} | |
//Normal binary search from here | |
if(strings[mid].compareTo(find) > 0) | |
return searchRec(strings, find, low, mid-1); | |
if(strings[mid].compareTo(find) < 0) | |
return searchRec(strings, find, mid+1, high); | |
return mid; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment