Algorithms Clrcular shlfted array It is given a sorted circu

Algorithms: Clrcular shlfted array

It is given a sorted circularIy shifted array. This is an array of sorted unique integers such that each eIement has been shifted k positions to the right with eIements wrapping around. In other words if the Iength of the array is L, the vaIue at index i in the sorted array will be at index (i+k) % L in the sorted circularIy shifted array.

Write pseudocode such that if you are given a sorted circuIarly shifted array, you wiII return the maximum eIement.

The code must run asymptotically faster than (n).

Solution

Linear search (Time Complexity: O(n)):

#include <stdio.h>

int findMaximum(int arr[], int low, int high)

{
int max = arr[low];
int i;
for (i = low; i <= high; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}

/* Driver program to check above functions */

int main()
{
int arr[] = {1, 30, 40, 50, 60, 70, 23, 20};
int n = sizeof(arr)/sizeof(arr[0]);
printf(\"The maximum element is %d\", findMaximum(arr, 0, n-1));
getchar();
return 0;
}

Binary search (Time Complexity: O(Logn)):

#include <stdio.h>

int findMaximum(int arr[], int low, int high)
{

/* Base Case: Only one element is present in arr[low..high]*/
if (low == high)
return arr[low];

/* If there are two elements and first is greater then
the first element is maximum */
if ((high == low + 1) && arr[low] >= arr[high])
return arr[low];

/* If there are two elements and second is greater then
the second element is maximum */
if ((high == low + 1) && arr[low] < arr[high])
return arr[high];

int mid = (low + high)/2; /*low + (high - low)/2;*/

/* If we reach a point where arr[mid] is greater than both of
its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
is the maximum element*/
if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
return arr[mid];

/* If arr[mid] is greater than the next element and smaller than the previous
element then maximum lies on left side of mid */
if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
return findMaximum(arr, low, mid-1);
else // when arr[mid] is greater than arr[mid-1] and smaller than arr[mid+1]
return findMaximum(arr, mid + 1, high);
}

/* Driver program to check above functions */
int main()
{
int arr[] = {1, 3, 50, 10, 9, 7, 6};
int n = sizeof(arr)/sizeof(arr[0]);
printf(\"The maximum element is %d\", findMaximum(arr, 0, n-1));
getchar();
return 0;