Search an Item in a sorted array with shifted elements

Question 1:
You are given a sorted array with shifted elements. Elements can be shifted to the left or right by 'i' number of places. The sign of 'i' denotes the direction of the shift. For positive 'i' direction of shift is right and left for negative 'i'.

For example, consider the sorted array 2, 3, 4, 8, 10, 11. A shift of 3 places to the right would be denoted by i=2 and the shifted array would look like this: 10, 11, 2, 3, 4, 8,
For i=-2, the shifted array would look like: 4, 8, 10, 11, 2, 3.Search an item 10 in the array.

http://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/
Question 2:
Find the minimum element in a sorted and rotated array
http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/

Question 3:
Alternatively, Given an array of unsigned integers which is initially increasing and then decreasing find the maximum value in the array
http://www.geeksforgeeks.org/find-the-maximum-element-in-an-array-which-is-first-increasing-and-then-decreasing/

Question 4:
Given a sorted and rotated array, find if there is a pair with a given sum
Given an array that is sorted and then rotated around an unknown point. Find if array has a pair with given sum ‘x’. It may be assumed that all elements in array are distinct.

http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/


Method 1:Binary Search [ Finding point of rotation ]
Find the pivot point, divide the array in two sub-arrays and call binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it.
OR
1)   Assuming that it is an increasing order sorted array that has been rotated, except for one index A[i] < A[i+1] always holds.

2)   When we pick the middle element, of a such an array, out of the two sub-arrays one will always be in a strictly increasing order.

3)   The point of rotation, would then simply lie in the second sub-array which is not strictly increasing. 

By the virtue of the above mentioned points, whenever we examine the two halves, the starting element will always lie in that half which is not in strictly increasing order. Now once we have decide how to go about doing the binary search, we need to decide what we have to search. We are not directly searching for an number here, but an index i such that A[i] > A[i+1], since this is not possible in a normal sorted array, the index 'i+1' is the pivot of rotation and A[i+1] is the smallest number in the array.

int pivotedBinarySearch(int arr[], int arr_size, int no)
{
   int pivot = findPivot(arr, 0, arr_size-1);
   if(arr[pivot] == no)
     return pivot;
   if(arr[0] <= no)
     return binarySearch(arr, 0, pivot-1, no);
   else
     return binarySearch(arr, pivot+1, arr_size-1, no);
}    


int findPivot(int arr[], int low, int high)
{
   int mid = (low + high)/2;  
   if(arr[mid] > arr[mid + 1])
     return mid;
   if(arr[low] > arr[mid])
     return findPivot(arr, low, mid-1);
   else
     return findPivot(arr, mid + 1, high);
}

Note: If point of rotation is given then we can directly continue with binary search keeping in mind the following point:

// Take care of scenarios where the shift is more
   // than the length of the array
   shift = shift % myArray.Length;

   // -ve shift can be seen as positive shift equal to
   // the length of the array - ( -ve shift)
   if (shift < 0)
       shift = myArray.Length + shift;

Alternatively If we will find Pivot without recursion,

int findSmallest(int* a, int length)

{

    if(length==0 || a==NULL)

        return -1;

         

    int start=0,end=length-1;

     

    while(start <= end)

    {

        int mid=(start+end)/2;

         

        // this is the standard comparison condition

        if(a[mid] > a[mid+1])

            return a[mid+1];

         

        // an extra comparison that adds the optimization that

        // if the mid element is the smallest one, there will not be

        // extra iterations

        if(a[mid] < a[mid-1])

            return a[mid];

             

         

        // the left half is in strictly increasing order

        // so we search in the second half

        if(a[mid] > a[start])

        {

            start = mid+1;

        }

        // The array is not rrotated so we simply

        // return the first element of the array

        else if(a[mid] >= a[start] && a[mid] <= a[end])

             return a[0];

          

        // the right half is in strictly increasing order

        // and hence we will search in the left half

         else

           end= mid-1;

         

    }

    return -1;

}

Time:O(logn)

Method 2:Recursive Without Finding Point of rotation

A sorted array, say: {1,2,3,4,5,6,7,8,9,10,11,12}, do right rotate through carry unknown times, and then it might become: {6,7,8,9,10,11,12,1,2,3,4,5}. Now we need get the index of a given number, say 4, from the array within O(log(n)) time.

We can think of it this way: take the middle element of array, if target is found, fine; if not, and then array become two parts, one is sorted array, the other is shifted sorted array. As illustrated as below diagram:



If the target falls into the sorted array half, we can simple do a binary search; otherwise, repeat this operation in the other half in recursive way. You can see this is divide-and-conquer algorithm. Obviously this is O(log(n)).

// // A typical binary search implementation // int _BinarySearch(unsigned int ShiftedArray[], unsigned int start,unsigned int end, unsigned int target) {     // Not found     if( start == end && ShiftedArray[start] != target) {        return -1;     }     unsigned int middle = start + (end - start)/2;     if(target == ShiftedArray[middle])     {        return middle;     } else if (target > ShiftedArray[middle]) {        return _BinarySearch(ShiftedArray, middle + 1, end, target);     } else {        return _BinarySearch(ShiftedArray, start, middle - 1, target);     } } // // Select a given number from shifted array. // ShiftedArray is something like = {6,7,8,9,10,11,12,1,2,3,4,5} // If found, return index of the number; if not, reutrn -1 // Require log(N) // int SearchShiftedArray(unsigned int ShiftedArray[], unsigned int start,unsigned int end, unsigned int target) {     // Start meets end     if( start == end && ShiftedArray[start] != target) {        return -1;     }     unsigned int middle = start + (end - start)/2;     if(target == ShiftedArray[middle])     {        return middle;     }      else if(ShiftedArray[middle] < ShiftedArray[start]) { // Right half is sorted linearly        if((target > ShiftedArray[middle]) && (target <= ShiftedArray[end])) {            return _BinarySearch(ShiftedArray, middle + 1, end, target);        } else {            return SearchShiftedArray(ShiftedArray, start, middle-1, target);        }     } else { // Left half is sorted linearly        if((target >= ShiftedArray[start]) && (target < ShiftedArray[middle])) {            return _BinarySearch(ShiftedArray, start, middle - 1, target);        } else {            return SearchShiftedArray(ShiftedArray, middle + 1, end, target);        }     } }

Test cases

Positive: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 3, target = 8 Negative: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 0, target = 13 Boundary: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 6, target = 5 Exceptional: {…max}, target = max

Method 2.2:Iterative without Pivot--Best Method

First, we know that it is a sorted array that’s been rotated. Although we do not know where the rotation pivot is, there is a property we can take advantage of. Here, we make an observation that a rotated array can be classified as two sub-array that is sorted (i.e., 4 5 6 7 0 1 2 consists of two sub-arrays 4 5 6 7 and 0 1 2.

Do not jump to conclusion that we need to first find the location of the pivot and then do binary search on both sub-arrays. Although this can be done in O(lg n) time, this is not necessary and is more complicated.

In fact, we don’t need to know where the pivot is. Look at the middle element (7). Compare it with the left most (4) and right most element (2). The left most element (4) is less than (7). This gives us valuable information — All elements in the bottom half must be in strictly increasing order. Therefore, if the key we are looking for is between 4 and 7, we eliminate the upper half; if not, we eliminate the bottom half.

When left index is greater than right index, we have to stop searching as the key we are finding is not in the array.

Since we reduce the search space by half each time, the complexity must be in the order of O(lg n). It is similar to binary search but is somehow modified for this problem. In fact, this is more general than binary search, as it works for both rotated and non-rotated arrays.

int rotated_binary_search(int A[], int N, int key) {

  int L = 0;

  int R = N - 1;

  while (L <= R) {

    // Avoid overflow, same as M=(L+R)/2

    int M = L + ((R - L) / 2);

    if (A[M] == key) return M;

    // the bottom half is sorted

    if (A[L] <= A[M]) {

      if (A[L] <= key && key < A[M])

        R = M - 1;

      else

        L = M + 1;

    }

    // the upper half is sorted

    else {

      if (A[M] < key && key <= A[R])

        L = M + 1;

      else

        R = M - 1;

    }

  }

  return -1;

}

If we are required to find the rotation point then we can proceed as follows

This problem is in fact the same as finding the minimum element’s index. If the middle element is greater than the right most element, then the pivot must be to the right; if it is not, the pivot must be to the left.

int FindSortedArrayRotation(int A[], int N) {

  int L = 0;

  int R = N - 1;

  while (A[L] > A[R]) {

    int M = L + (R - L) / 2;

    if (A[M] > A[R])

      L = M + 1;

    else

      R = M;

  }

  return L;

}

Useful Link:

http://www.leetcode.com/2010/04/searching-element-in-rotated-array.html

Solution if duplicates are allowed:

#include <iostream>

int rotatedSearch(int values[], int start, int end,int x)
{
    if(values[start] == x){
        return start;
    } else if(values[end] == x){
        return end;
    } else if(end - start == 1) {
        return -1;
    }
    int middle = (start + end) / 2;

    
    if((values[start]==values[middle]) && (values[middle] == values[end]))
        { 
          if((rotatedSearch(values, start, middle, x))!=-1)
              return rotatedSearch(values, start, middle, x);
          else    
               return rotatedSearch(values, middle, end, x);
        }
               
    if(values[start] <= values[middle]){
        if(x <= values[middle] && x >= values[start]){
            return rotatedSearch(values, start, middle, x);
        } else {
            return rotatedSearch(values, middle, end, x);
        }
    } else if(values[middle] <= values[end]){
        if(x >= values[middle] && x <= values[end] ){
            return rotatedSearch(values, middle, end, x);
        } else {
            return rotatedSearch(values, start, middle, x);
        }
    } else {
        return -1;
    }
}

int main()
{
 //  int arr[12] = {1, 2, 2, 3, 4, 5, 6, 7, 1, 1, 1, 1};
   int arr[13] = {1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1};
  //int arr[13] = {1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1};
   printf("Index of the element is %d", rotatedSearch(arr, 0,11, 2)); 
   getchar();
   return 0;
}

Question 2:Modified Binary Search to find maximum element
int search(int* arr, int strt, int end)
{
    int mid = (strt+end)/2;

    if((arr[mid-1] < arr[mid]) &&  (arr[mid] > arr[mid+1]))
        return arr[mid];
    else if(arr[mid-1] < arr[mid])
        return search(arr, mid+1, end);
    else if(arr[mid] > arr[mid+1])
        return search(arr, strt, mid-1);
}

int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 6, 5, 4};

    printf("%d\n", search(arr, 0, 9));
    return 0;
}