## Interview Questions

### Find first shifted number.

Sorted array has been shifted. For example 4, 5, 7, 9, 1, 2. Find position of the first number in the shifted section of the array (in this case 1).

View Solution

#### Algorithm concept

Easiest way to solve this problem is to iterate through all elements in the array and find first element that is smaller than previous one. In sorted array next element should be always equal or greater than the previous one. Once we find the element that does not match this condition, this element is our "pivot" which indicates position where array has been shifted.

The above solution is the simplest and you might assume that this is not what interviewer expects. Interviewer expects something better. Much better way to find this is to use Binary Search algorithm. This algorithm will need to be modified to check for this condition.

Best way to start is to implement Binary Search algorithm and then modify it to check for this condition.

#### Complexity

The solution uses Binary Search algorithm. Complexity of this algorithm is O(logn).

#### Partial solution (Binary Search implementation)

int binarySearch(int *array, int first, int last, int k)
{
if (first > last) { return -1; }
while (first <= last)
{
// the below is prefered vs (first+last)/2,
// because it solves potential integer overflow
int index = first + (last-first) / 2;
int elem = array[index];
if (elem == k)
{
// found element
return index;
}
else if (elem > k)
{
// search in left part
last = index - 1;
}
else
{
// search in right part
first = index + s1;
}
}
return -1;
}

#### Solution - if no duplicates

**Note: Below algorithm will only work if there are no duplicates**

int findShiftedUsingBinarySearch(int *array, int first, int last)
{
int absoluteFirst = first;
if (first > last) { return -1; }
while (first <= last)
{
// the below is prefered vs (first+last)/2,
// because it solves potential integer overflow
int index = first + (last - first) / 2;
int elem = array[index];
int prevElem = elem;
if (index > absoluteFirst)
{
prevElem = array[index - 1];
}
if (prevElem > elem)
{
// found shifted element
return index;
}
else if (prevElem < elem)
{
// left part is sorted - search in right part
first = index + 1;
}
else
{
// element is equal to left one - search in left part
last = index - 1;
}
}
// no element is shifted
return -1;
}