CareerCup

1. pick the middle and check

a. A[mid-1]<A[mid]<A[mid+1] if true, this means the transition point is between mid and the right
b. A[mid-1]>A[mid]>A[mid+1] if true, this means the transition point is between mid and the left

also check if

c. A[mid-1]<A[mid] && A[mid]> A[mid+1] this means the mid is the transition point.

recursively pick the side that contains the transition point.

public static int findMax(int[] A, int left, int right){
	    if(right-left==1){
	        if(A[left]>A[right])
	            return left;
	        else
	            return right;
	    }
	    int mid = (left+right)/2;
	    if(A[mid]>A[mid-1] && A[mid]>=A[mid+1]){
	        return mid;
	    }
        if(A[mid]>A[mid-1] && A[mid]<=A[mid+1]){
            return findMax(A, mid+1, right);
        }
        if(A[mid]<A[mid-1] && A[mid]>=A[mid+1]){
            return findMax(A, left, mid-1);
        }	    
	    return -1;
	}

Its like increasing slope and then decreasing slope. We have to find the highest point.

That highest point cud be found out by using binary search, and check if

a[mid-1] a[mid] a[mid+1] is in increasing or decreasing order.

if increasing , move to right half
if decreasing, move to left half

Stopping criteria: a[mid-1] < a[mid] > a[mid+1]

binary search?

I presume k is not known, and that is an important piece of info which you ought to provide.

This is a variation of - If a sorted array has been rotated (circularly) then find the maximum element.
(1 2 3 4 5) rotated to (4 5 1 2 3)

int FindMax(int A[], int size)
{
  return FindMaxRec(A, 0, size - 1);
}

int FindMaxRec(int A[], int start, int end)
{
  if (start == end)
  {
    return A[start];
  }

  int mid = (start + end) / 2;

  if (A[mid - 1] < A[mid] && A[mid + 1] < A[mid]) return A[mid];
  
  if (A[mid - 1] < A[mid]) return FindMaxRec(A, mid + 1, end);

  return FindMaxRec(A, start, mid - 1);
}

heyyyy........i think we have to compare the Kth and k+1 th element to get the max element.......let me know its right or not.

u mean to say he will tell value of k and u need to find that number at kth position
:P

perform bitonic sort

If till K array is in ascending order then Kth element is highest element (0, k) and then if array is in descending then K+1st element in highest among rest (K+1, nth)
So, compare highest elements in each partition i.e k and k+1st element
return max(a[k], a[k+1]).

int method(int a[],int n)
{
	int m,l=0,r=n;
	
	while(l<r)
	{
		m=(l+r)/2;
		if(m>0 && m<n)
			{
			if(a[m-1] <= a[m] )
			{
				if( a[m] <= a[m+1])
					l=m+1;
				else
					break;
			}
			else
				r=m-1;
			}
		else
			break;
	}
	
	cout<<a[m];
return 0;
}

int max(int[] num)
{
int i = 0;
while (i < num.Length)
{
while (num[i] < num[i + 1])
i++;
break;
}
return num[i];
}

Acc. to this code we don't need the value of k, since it is sorted in ascending order till k and descending order (k+1) onwards, we can get the answer with the following code.
Am I missing anything ?

int max(int[] num)
{
int i = 0;
while (i < num.Length)
{
while (num[i] < num[i + 1])
i++;
break;
}
return num[i];
}

I think the array would be like 1,2,3,4,5,6,10,9,8,7 OR 1,23,4,5,6,12,11,10,9. So, we need to arrive at the kth value and then, we need to identify if kth value is f=greater than the k+1th value. I think you missed that.

How do you think?

Thanks,
-Pavan.