Interview Questions

176. Given a sorted array with duplicates and a number.......

Microsoft Interview Questions and Answers


(Continued from previous question...)

176. Given a sorted array with duplicates and a number.......

Question:
Given a sorted array with duplicates and a number, find the range in the form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).

Upon further probe:
1. Do better than linear scan, which is O(n). 2. You can just work out how to find the start index, and I will assume that you know how to find the end.


maybe an answer:


int BsearchStartIndex( int *A, int start, int end, int key )
{
int mid = ( start + end )/2;
if( (start == end ) )
{
if( (A[mid] == key) )
{
return start;
}
else
{
return -1; // key not exists
}
}
else if( A[mid] < key )
{
start = mid +1 ;
}
else if( A[mid] > key)
{
end = mid -1;
}
else // A[mid] == key
{
if (A[mid-1] != A[mid])
return mid;
}
return BsearchStartIndex( A, start, end, key );
}

int BSearchEndIndex( int *A, int start, int end , int key )
{
int mid = ( start + end )/2;
if( (start == end ))
{
if( (A[mid] == key) )
{
return end;
}
else
{
return -1; // key not exists
}
}
else if( A[mid] > key )
{
end = mid -1 ;
}
else if( A[mid] < key )
{
start = mid +1 ;
}
else
{
if ( A[mid] != A[mid+1])
return mid;
}
return BsearchStartIndex( A, start, end, key );
}

int main()
{
startIndex = BsearchStartIndex( A, 0, n-1, key );
if (startIndex == -1) endIndex = -1;
else
endIndex = BsearchEndIndex( A, startIndex, n-1, key );
}

(Continued on next question...)

Other Interview Questions