HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Java binary search (and get index if not there) review

Submitted by: @import:stackexchange-codereview··
0
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?

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

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.