Consider the binary search algorithm in Section 14.6. If no match is found, the
ID: 654180 • Letter: C
Question
Consider the binary search algorithm in Section 14.6. If no match is found, the search method returns -1. Modify the method so that if a is not found, the method returns -k - 1, where k is the position before which the element should be inserted. (This is the same behavior as Arrays.binarySearch.)
public class BinarySearcher
{
public int search(int[] a, int low, int high, int value)
{
if(low <= high)
{
int mid = (low + high)/2;
if(a[mid] == value)
{
return mid;
}
else if (a[mid] < value)
{
return search(a, low, mid + 1,high, value);
}
else
{
return search(a, low, mid-1, value);
}
}
else
{
return -1;
}
}
}
Explanation / Answer
public class BinarySearcher
{
public static int search(int[] a, int low, int high, int value)
{
if(low <= high)
{
int mid = (low + high)/2;
if(a[mid] == value)
{
return mid;
}
else if (a[mid] < value)
{
return search(a, mid + 1,high, value);
}
else
{
return search(a, low, mid-1, value);
}
}
else
{
return -low-1;
}
}
}