CareerCup

Can be done in O(log n).
int find_index(int *a,int start,int end)
{
int index=(start+end)/2;
if(a[start]<a[index]<a[end])
return start;
else if(a[start]>a[index])
return find_index(a,start,index);
else if(a[index]>a[end])
return find_index(a,index,end);

}

But I don't understand the use of 'million' numbers here.
Can somebody explain me what all should we look for in general when questions involving large arrays are given.

scan the whole array ,compare with the previous element, if less than, this is the start index, o(n)
2.binary search

any way the array is sorted and weather its rotating clock wise or not the starting position will be 0th location right.

Joe's answer is right.
Only thing is what if array is not rotated at all or array rotated million time (the lenght of array).

Need to put one more condition:
if go through whole array, and can not find previous element greater than the current then starting point is first element in array.

"million" number is just to make thing little challanging.

Million could have been used to give a hint that O(log n) solution is very important for the problem. log of 1 million will be much smaller than O(n) in this case

You guys are missing something. What if the array elements are allowed to repeat?

For instance the array was 0,0,0.....,0, 1 and then rotated by unknown quantity. How do you find out where the rotation starts in O(logn) time?

In case the elements are known to be unique, then an O(logn) solution exists as pointed out by "yeah".

Can be done in O(log n).

int findstart(int *a,int beg,int end)
{
int mid=(beg+end)/2;
if(beg==mid)
return end;

else if(a[beg]>a[mid])
return findstart(a,beg,mid);

else if(a[mid]>a[end])
return findstart(a,mid,end);

else if(a[beg]==a[mid] && a[mid]==a[end]) // if all 3 are same for cases like
{ // 9 9 9 1 9
if(findstart(a,beg,mid)==a[beg]) // if the starting point returned is same
return findstart(a,mid,end); // as a[beg] i.e the equal value as '9' in
// the above case move to the other half
else
return findstart(a,beg,mid); // if the other half also returns the same
} // value then array contains only 1 unique
} // element

Sample
Initial - 1 1 3 4 4 6 7
Rotated - 6 7 1 1 3 4 4
b m e

b m e

b m e

'b'e
'm'

Initial - 0 1 6 6 6 6 6
Rotated - 6 6 6 6 0 1 6
b m e
s

b m e

'b'e
'm'

Here in both cases b==m at last step and the value end is the index. It is to be noted that whatever the input is the algorithm takes log(n) time.

The code works for cases like 9 9 9 9 0 0 5 also and 9 9 9 9 0 1 9 or even all elements same value.
But for worst case and best case it takes O(logn). And it does take care of repetiton too.

sorry i din know how to preserve the white space. so only the confusion.

sorry i din know how to preserve the white space. so only the confusion.

sorry i din know how to preserve the white space. so only the confusion.

ok.. be careful next time...

int FindPointOfRotation(int a[], int len)
{
	if(!a || (len < 0))
		return -9999;
	if(len == 1)
		return 0;
	int low = 0; int high = len - 1;
	while(low < high)
	{
		int mid = (low + high) / 2;
		if(a[mid] <= a[high])
		{
			if((mid == 0) || (a[mid - 1] > a[mid]))
				return mid;
			else
				high = mid - 1;
		}
		else
		{
			if(a[mid + 1] < a[mid])
				return mid + 1;
			else
				low = mid + 1;
		}
	}
	return 0;
}

Above code doesnt work for

{1, 1, 1, 1, 1, 1, 2, 1}

Here is another one:

int findRotation(int *array, int length)
{
	if (!length || 1 == length) return 0;
	int start = 0;
	int end = length - 1;
	if (array[start] < array[end])
		return 0;
	int middle;
	while (start != end)
	{
		middle = (start + end) / 2;
		if (array[start] > array[middle])
		{
			if (array[middle + 1] > array[end])
				start = middle + 1;
			else if (array[middle] > array[middle + 1])
				return middle + 1;
			else
				end = middle;
		}
		else
			return middle + 1;
	}
}

O(n) can be reduced in some cases by splitting the array in to (n/2) and check whether the first < (n/2 + 1 th) element and continue in the second part if it is true or do the same in the first part of the array
tis might reduce O(n)!!

Modified binary search - log(n)