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).
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.
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; }
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; }