CareerCup

how about doing it without finding the maximum element ? Any idea..?

No, u can't because to do this in better than o(n) u need sorted arrays. So definitely u need to find the peak.

It can be done without finding the peak, same complexity though. Only takes two binary searches instead of three, however.

Take, as an example, the array {1, 4, 5, 7,,10, 11, 9, 6, -1}
And, while looking for 6 through some variant of binary search, I get the two sub arrays {1,4,5} {7,10,11,9,,6-1}. See if you notice something interesting about the arrays.

@SycophantEve

Let me see if I got this right.

When you do a binary search, you might not find it, so you split up left and right on where your failed binary search is. At this point, if you look at the last two values of the left subarray and first two values of the right sub array, you can figure out which side the peak is on.

In your example. 1,4,5 means the left subarray is increasing which means peak is in the right sub array.

Now when you do the binary search on the right sub array, we can do a modified binary search in that we know there's a peak and two sides but only one side will have possible search because the other side is already bounded when we did the left/right subarray split. So your example 7, 10, 11, 9, 6, -1 ... peak is at 11, but we know the 6 must be on the right side of the peak because when we cut the array in two previously, we know the left side is already greater than 6. So you do a binary search... if the mid value is greater than 6 you binary search right, if a mid value is less than 6 you binary search left (reverse)

Did I get the gist of thing?

@SycophantEve

Let me see if I got this right.

When you do a binary search, you might not find it, so you split up left and right on where your failed binary search is. At this point, if you look at the last two values of the left subarray and first two values of the right sub array, you can figure out which side the peak is on.

In your example. 1,4,5 means the left subarray is increasing which means peak is in the right sub array.

Now when you do the binary search on the right sub array, we can do a modified binary search in that we know there's a peak and two sides but only one side will have possible search because the other side is already bounded when we did the left/right subarray split. So your example 7, 10, 11, 9, 6, -1 ... peak is at 11, but we know the 6 must be on the right side of the peak because when we cut the array in two previously, we know the left side is already greater than 6. So you do a binary search... if the mid value is greater than 6 you binary search right, if a mid value is less than 6 you binary search left (reverse)

Did I get the gist of thing?

Pretty much. The idea is, that given any array that is sorted in this way, we can find two things. 1. Which side the peak is on and 2. If we find an element greater than the element we're looking for, then the left side sub array is sorted in increasing order relative to what we're looking for and the right side is sorted in decreasing order relative to what we're looking for.

{1, 4, 5, 7,8, 9,10, 9, 6, -1}

So we check mid = 8
It's greater than 6 so we break up the arrays
{1, 4, 5, 7} {9,10,9,6,-1}.
So even though either array may be unsorted, they still have the invariant required for binary search. In that on the right side, everything that is greater than the element we're looking for is before our element.

Basically you do a binary search, moving closer to the peak each time if the middle element is less than what we're looking for. After we find any element greater than the searched for element, we do a ascending order binary search on the left half and a descending binary searchon the right.

Basically the trick is, the sub arrays are "sorted enough" as long as you split at an element > than the search for element.

In the example above, you also notice that the right array is "sorted enough".

Nice approach. However, I don't think the time calculation is correct since the max element will not always be in the center.

//Supporting functions:

int findPeak(int * myArr, int mySize)
{
//Find Peak Element
	if (mySize  == 0 || mySize == 1)
	{
		return 0;
	}

	int h = mySize - 1;
	int l = 0;
	int m = (l + h)/2;

	while(l <= h)
	{
		
		if (l == h)
		{
			cout << "Peak element idx is " << l << endl;
			return l;
		}
		m = (l+h)/2;
		//cout << "low" << myArr[l] << " med" << myArr[m] << " high" << myArr[h] << endl;
		if (myArr[m] > myArr[m-1] && myArr[m] > myArr[m+1])
		{
			cout << "Peak element is at idx" << m << endl;
			return m;
		}
		if(myArr[m] > myArr[m-1])
		{
			//cout << "peak in upper half" << endl;
			l = m+1;
			cout << " l:" << l << endl;
		}
		else
		{
			//cout << "peak in lower half" << endl;
			h = m-1;
			cout << " h: " << h << endl; 
		}
	}
	return 0;
}


bool binarySearch(int *Arr, int start_Idx, int end_Idx, int element)
{
	if (start_Idx > end_Idx)
	{
		cout << "err" << endl;
		return false;
	}
	if (start_Idx == end_Idx)
	{
		if (Arr[0] == element)
		{
			cout << "binarySearch found element at idx 0" << endl;
			return true;
		}
		else
		{
			cout << "binarySearch Not found" << endl;
			return false;
		}	
	}
	int l = start_Idx;
	int h = end_Idx;
	int m = 0;

	while (l <= h)
	{
		m = (l+h)/2;
		//cout << "binarySearch l " << l << " m " << m << " h " << h << endl;
		
		if (Arr[m] == element)
		{
			cout << "binarySearch Found element at idx" << m << endl; 
			return true; 
		}
		else if (Arr[m] > element)
		{
			//cout << "binarySearch Element in lower half" << endl;
			h = m-1;
		}
		else
		{
			//cout << "binarySearch Element in upper half" << endl;
			l = m+1;
		}
	}
	cout << "binarySearch Element not found" << endl; 	
	return false;
}

bool invertedBinarySearch(int *Arr, int start_Idx, int end_Idx, int element)
{
//Binary search for a decreasing array. E.g. {9, 8, 7, 6}
	if (start_Idx > end_Idx)
	{
		cout << "err" << endl;
		return false;
	}
	if (start_Idx == end_Idx)
	{
		if (Arr[0] == element)
		{
			cout << "invertedBinarySearch found element at idx 0" << endl;
			return true;
		}
		else
		{
			cout << "invertedBinarySearch Not found" << endl;
			return false;
		}	
	}
	int l = start_Idx;
	int h = end_Idx;
	int m = 0;

	while (l <= h)
	{
		m = (l+h)/2;
		//cout << "binarySearch l " << l << " m " << m << " h " << h << endl;
		
		if (Arr[m] == element)
		{
			cout << "invertedBinarySearch Found element at idx" << m << endl; 
			return true; 
		}
		else if (Arr[m] > element)
		{
			//cout << "binarySearch Element in lower half" << endl;
			l= m+1;
		}
		else
		{
			//cout << "binarySearch Element in upper half" << endl;
			h = m-1;
		}
	}
	cout << "invertedBinarySearch Element not found" << endl; 	
	return false;
}

// Main functions:

void findElement(int *Arr, int size, int element)
{
	if(size == 0)
	{
		cout << "err" << endl;
		return;
	}
	if(size == 1)
	{
		if (Arr[0] == element)
		{
			cout << "Found element at idx 0" << endl;
			return;
		}
		else
		{
			cout << "Not found" << endl;
			return;
		}
	}
	int peak = findPeak(Arr, size);
	int l1 = 0; int h1 = peak;
	int l2 = peak+1; int h2 = size;
	
	if (binarySearch(Arr, l1, h1, element) || invertedBinarySearch(Arr, l2, h2, element))
	{
		cout << "element found" << endl;
	}
	else
	{
		cout << "element not found" << endl;
	}
	return;
}

int main()
{
	int A[9] = {1,2,3,5,7,9,11};
	int B[9] = {11,9,7,5,3,2,1};
	int C[9] = {1,2,5,8,13,9,3,-1};
	findElement(C, 7, 3);
	return 0;
}

Compilation warnings aside, your getPoint() function is wrong, and consequently the whole algorithm doesn't work.

Counter-example:

Find 6 in [ 6, 20, 15, 12, 11, 10, 9 ].

Hint: getPoint() will mistakenly recurse on array[4..6] looking for the maximum.

@ 010010.bin sry my bad, i thought input as kinda rotated array like:-
a.....Peak.....b, i took all elemnts right of Peak as smaller than a, which isn't the case.
As far as compilation error, i posted the running code (on DevC++) for gcc, need to comment system("PAUSE") .

with the same example you gave, what if i'm searching for 6? 6 is also smaller than ar[mid], but you won't find 6 at (mid+1, n).