Microsoft Interview Question
Senior Software Development EngineersCountry: United States
Simple trick.
[1] Do a binary search to find lowest value index in array.
[2] Then just a regular binary search to look for target value, but use index from [1] to accommodate for rotation.
#include<iostream>
#include<vector>
using namespace std;
const int notFoundError = -1;
int findElement( const vector<int>& input, const int target )
{
// Do a binary search and find lowest element in array
int lo=0;
int hi = input.size()-1;
while( lo < hi)
{
int mid = lo + (hi- lo)/2;
if( input[mid] > input[hi] )
{
lo = mid+1;
}
else
{
hi = mid;
}
}
// save index of minimum value
int minIndex = lo;
// reset lo and hi
lo = 0;
hi = input.size()-1;
// we do binary search for original element
while( lo <= hi)
{
int mid = lo + (hi- lo)/2;
int realMid = ( mid+ minIndex) % input.size();
if( target == input[realMid] )
{
return realMid;
}
else if( target > input[realMid] )
{
lo = mid+1;
}
else{
hi = mid-1;
}
}
return notFoundError;
}
int main()
{
vector<int> input({7,8,2,4,5, 6});
cout << findElement(input, 5);
return 0;
}
Let A the original sorted array of length N and R the result of rotating A to the right K times, 0 < K <= N (if K = N the array didn't rotate at all). We can observe the mapping R[i] = A[(i + K) mod N], so if we know K, we can run a binary search on R mapping positions to A!
If R[0] < R[N - 1], A didn't rotate, and we set K = N. Otherwise, R can be splitted in two halves A and B, such that every element in B is less than any element in A. K is the length of the half A.
We use binary search as follows with R[0] as pivot to find K.
findK(R, N)
if R[0] < R[N - 1]
return N
lo := 1
hi := N - 1
while lo <= hi
mid := (lo + hi) / 2;
if R[mid] > R[0]
lo := mid + 1
else if R[mid - 1] >= R[0]
return mid
else
hi := mid - 1
Binary search to find element would be as follows
findValue(R, N, value)
K := findK(R, N)
lo := 0
hi := N - 1
while lo <= hi
mid := (lo + hi) / 2
if R[(mid + K) % N] = value
return true
else if R[(mid + K) % N] < value
lo := mid + 1
else
hi := mid - 1
return false
Time complexity is O(log N) and O(1) extra space.
Solution in Java:
public class FindElementInSortedRotatedArray {
private static int findElement(int [] input, int target){
if(input == null || input.length == 0){
return -1;
}
int start = 0;
int end = input.length - 1;
int mid = (start + end)/2;
for(int i = 0; i < input.length; i++){
// check if start to mid of input array is sorted
if(input[start] <= input[mid]){
// check if target element lies between start and mid
if(input[start] <= target && target <= input[mid]){
// if target lies with start and mid, set end pointer to mid-1
end = mid - 1;
}
else{
start = mid + 1;
}
}
// then check if mid to end of input array is sorted
else {
if(input[mid] <= target && target <= input[end]){
// set start pointer to mid + 1
start = mid + 1;
}
else {
end = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
{
int array[] = { 56, 58, 67, 76, 21, 32, 37, 40, 45, 49 };
findElementUsingBinarySearchTest(array, 45);
}
}
private static void findElementUsingBinarySearchTest(int[] array, int num) {
System.out.println("Element " + num + " found at = " + findElement(array, num));
}
}
public static int binarySearchRotated(int [] arr, int val){
//calculate step count
int step = 1;
int i = 1;
while (arr[i]>=arr[i-1]){
step++;
i++;
}
//rotate back
step = arr.length - step;
rotate(arr,step);
//regular binary search
return binarySearchIter(arr,val) ;
}
public static int binarySearchIter(int [] arr, int val){
int low = 0, high = arr.length-1;
while (low <= high){
int mid = (low + high)/2;
if(arr[mid] == val){
return mid;
} else if(val < arr[mid]){
high = mid-1;
} else {
low = mid + 1;
}
}
return -1;
}
public static void reverse(int [] arr, int start, int end){
while (start < end){
int tmp = arr[end];
arr[end] = arr[start];
arr[start] = tmp;
end--;
start++;
}
}
public static void rotate(int [] arr, int step){
//rotate the array to the right by k steps
step %= arr.length;
reverse(arr,0,arr.length-1);
reverse(arr,0,step-1);
reverse(arr,step,arr.length-1);
}
- Alex October 31, 2017