CareerCup

//
int countrot(int a[], int low, int high)
{
int mid = (low+high)/2;

if (a[mid] > a[low]) {
return countrot(a, mid, high);
}
if (a[mid] < a[high]) {
return countrot(a, low, mid);
}
if (a[mid] > a[mid+1]) {
return (mid+1);
}
return 0;
}//

//
int countrot(int a[], int low, int high)
{
int mid = (low+high)/2;

if (a[mid] > a[low]) {
return countrot(a, mid, high);
}
if (a[mid] < a[high]) {
return countrot(a, low, mid);
}
if (a[mid] > a[mid+1]) {
return (mid+1);
}
return 0;
}//

As the array currently is not sorted ,a direct Binary search will not give us the desired result. we know that sorted array is rotated based on a position of a element
1234567 after rotation on 3 becomes 3456712 . we calculate the distance from mid element to the rotation element , in our case its 1(Let it be X) .
so after rotation we increment/decrement by X to get the pivot element , form a binary tree from by choosing this element as pivot element.
Then we can search any node Log(n) order.

Let len be the length of the array. When array is rotated at position n the resulting elements ar[0..(len-n)] and ar[(len-n)..len] are still sorted. Do a binary search among these sorted arrays to find the element.

public static void searchRotate()
	{
		int a[]={6,7,8,1,2,3,4,5};
		int lt=0,rt=a.length-1,mid=0;
		int find = 3;
		boolean found =false;
		while(lt<=rt)
		{
			mid = (lt+rt)/2;
			if(a[mid] == find)
			{
				System.out.println("Found at index:"+mid);
				found =true;
				break;
			}
			if(a[mid] <= a[rt])
			{
				if(find>a[mid] && find<=a[rt])
				{
					lt = mid+1;
				} else {
					rt = mid -1;
				}
			} else if(a[lt] <= a[mid] )
			{
			  if(find>a[lt] && find <=a[mid])
			  {
				  rt = mid -1;
			  } else {
				  lt = mid +1;
			  }
			} 
		}
		if(!found)
			System.out.println("Element not found");
	}

Do two binary searches. One to find the smallest element in the array, that is the actual starting point of the sorted array. Second to find the element that is required. Two binary searches is lg n + lg n = lg n

As per "ap on January 19, 2011"

/**
 * * @author hmm :  To find the rotation point in O(log n)
 * 
 */
public class Main {

   public static int array[]={6,7,8,9,10,1,2,3,4,5};
    public static void main(String[] args)
        {
            int low = 0;
            int high = array.length;
            int mid = 0;

            while(low<high)
                {
                    System.out.println("low = "+low +" high " + high);

                    mid = (low + high)/2;
                    if(array[mid] > array[low])
                        //Turning point is towards the left
                        low=mid;
                    else
                        //Turning point is towards the right
                        high=mid;

                }

            System.out.println("Rotated around "+ array[low]);
            /* Binary Search */
          }

}

First- for "ap on January 19, 2011"
You can't find the smallest in a cyclically sorted array in Binary search
Consider {20, 50, 2, 4, 7, 9, 11, 19}
half-point is {4} and then {50} and then what- {20}?

Second- for everyone
Is this solution O(lg n) ?
findOffset(array A)
//Recursive stops
if A's size equals 1 return 0
if A's size equals 2 return 0 if A[0]<A[1] and 1 otherwise

set rightSideVal = findOffset(right side of A)
//if the right size is cyclic then all the left side is part of that shift
if rightSideVal > 0 then rightSideVal += A's size / 2
return findOffset(left half of A) + rightSideVal

For solving the above algorithm we will need to use the binary search in the sorted and rotated array we will first find the mid using (high + low) / 2 and we will check for the condition that the mid element must be greater then the lower index element and then, if yes we will again check for the element being between the low and the mid index if found then traverse the low to mid - 1 else we will traverse the mid + 1 to high subarray, and the next condition will be the opposite of the first.

Implementation:

int findlement(int arr[], int low, int high, int key){
	if(low > high)
		return -1;
	int mid = (high + low) / 2;
	if(arr[mid] == key)
		return mid;
	if(arr[mid] > arr[low]){
		if(key >= arr[low] && key <= arr[mid])
			return findelement(arr, low , mid - 1, key);
		return findelement(arr, mid + 1, high, key);
	}
	if(arr[mid] >= key && key <= arr[high])
		return findelement(arr, mid + 1, high, key);
	return findelement(arr, low , mid - 1, key);
}