I am attempting to expand a function to find the number of integer matches through Binary Search by resetting the high variable, but it gets stuck in a loop. I am guessing a workaround would be to duplicate this function to obtain the last index to determine the number of matches, but I do not think this would be such an elegant solution.
From this:
public static Matches findMatches(int[] values, int query) {
int firstMatchIndex = -1;
int lastMatchIndex = -1;
int numberOfMatches = 0;
int low = 0;
int mid = 0;
int high = values[values.length - 1];
boolean searchFirst = false;
while (low <= high){
mid = (low + high)/2;
if (values[mid] == query && firstMatchIndex == -1){
firstMatchIndex = mid;
if (searchFirst){
high = mid - 1;
searchFirst = false;
} else {
low = mid + 1;
}
} else if (query < values[mid]){
high = mid - 1;
} else {
low = mid + 1;
}
}
if (firstMatchIndex != -1) { // First match index is set
return new Matches(firstMatchIndex, numberOfMatches);
}
else { // First match index is not set
return new Matches(-1, 0);
}
}
To something like this:
public static Matches findMatches(int[] values, int query) {
int firstMatchIndex = -1;
int lastMatchIndex = -1;
int numberOfMatches = 0;
int low = 0;
int mid = 0;
int high = values[values.length - 1];
boolean searchFirst = false;
while (low <= high){
mid = (low + high)/2;
if (values[mid] == query && firstMatchIndex == -1){
firstMatchIndex = mid;
if (searchFirst){
high = values[values.length - 1]; // This is stuck in a loop
searchFirst = false;
}
} else if (values[mid] == query && lastMatchIndex == -1){
lastMatchIndex = mid;
if (!searchFirst){
high = mid - 1;
} else {
low = mid + 1;
}
} else if (query < values[mid]){
high = mid - 1;
} else {
low = mid + 1;
}
}
if (firstMatchIndex != -1) { // First match index is set
return new Matches(firstMatchIndex, numberOfMatches);
}
else { // First match index is not set
return new Matches(-1, 0);
}
}
There is a problem with your code:
high = values[values.length - 1];
should be
high = values.length - 1;
Also you do not need variables like numberOfMatches and searchFirst, we can have rather simple solution.
Now coming to the problem,I understand what you want I think Binary Search is appropriate for such query.
The Best way to do the required is once a match is found you just go forward and backward from that index until a mismatch occurs and this would be both elegant and efficient in calculating the firstMatchIndex and numberOfMatches.
So your function should be:
public static Matches findMatches(int[] values, int query)
{
int firstMatchIndex = -1,lastMatchIndex=-1;
int low = 0,mid = 0,high = values.length - 1;
while (low <= high)
{
mid = (low + high)/2;
if(values[mid]==query)
{
lastMatchIndex=mid;
firstMatchIndex=mid;
while(lastMatchIndex+1<values.length&&values[lastMatchIndex+1]==query)
lastMatchIndex++;
while(firstMatchIndex-1>=0&&values[firstMatchIndex-1]==query)
firstMatchIndex--;
return new Matches(firstMatchIndex,lastMatchIndex-firstMatchIndex+1);
}
else if(values[mid]>query)
high=mid-1;
else low=mid+1;
}
return new Matches(-1,0);
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments