patternjavaMinor
Java binary search (and get index if not there) review
Viewed 0 times
searchjavagetbinaryandindextherenotreview
Problem
I want to do binary search and if the target is not there get the index of where it should have been.
This is the code I came up with. It seems correct. Is there any problem? Can it be improved?
This is the code I came up with. It seems correct. Is there any problem? Can it be improved?
private int binarySearch(String[] sortedArray, String target, int start, int end) {
if(start <= end){
int mid = (start + end)/2;
if(sortedArray[mid].equals(target)){
return mid;
}
else if (target.compareTo(sortedArray[mid]) < 0){
return binarySearch(sortedArray, target, start, mid - 1);
}
else{
return binarySearch(sortedArray, target, mid + 1, end);
}
}
return start;
}Solution
2 minor things:
-
Remove the unnecessary comparison. If
fails, it will again compare the two strings in the next
-
To keep the method signature simple, you can overload it and delegate to the one that does the work:
-
Remove the unnecessary comparison. If
sortedArray[mid].equals(target)fails, it will again compare the two strings in the next
if condition. Instead, you can just do:int c = target.compareTo(sortedArray[mid]);
if(c == 0)
return mid;
else if(c < 0)
...-
To keep the method signature simple, you can overload it and delegate to the one that does the work:
public int binarySearch(String[] sortedArray, String target) {
binarySearch(sortedArray, target, 0, sortedArray.length - 1);
}Code Snippets
sortedArray[mid].equals(target)int c = target.compareTo(sortedArray[mid]);
if(c == 0)
return mid;
else if(c < 0)
...public int binarySearch(String[] sortedArray, String target) {
binarySearch(sortedArray, target, 0, sortedArray.length - 1);
}Context
StackExchange Code Review Q#8388, answer score: 5
Revisions (0)
No revisions yet.