CareerCup

keep a pointer for initial address and 2nd pointer to search.
search till 2nd pointer != 1st one

Is the rotated array a sorted array rotated by some elements?
If yes then may be we can find the start index of the original array and apply binary search.

If the sorted array is rotated by some element say k, then we can find that index and apply binary search on individual sub-array to get the result..

sorry for many typos..i was in hurry..

its a search problem in sorted rotated array..simple enuf..most famous interview prob

<pre lang="c" line="1" title="CodeMonkey47968" class="run-this">#include <stdio.h>


// This subroutine finds how many places (k) the sorted array is rotated
// uses divide and conquer to find k... takes O(log n) time

int find_rotation(int a[],int len){
int i=0;

int start=0;
int end=len-1;
int mid=(start+end)/2;;

while(a[mid]<a[mid+1]){

if(a[mid]>a[start]) // the rotation is in the second subpart
start=mid;
else
end=mid;
mid=(start+end)/2;
}

return mid;
}

// Doing a binary search ... O(log n)

int search(int a[],int start,int end,int key){
if(start > end) return -1; // returns -1 if key is not found
int mid=(start+end)/2;
if(a[mid]==key) return mid;
if(a[mid]>key) return search(a,start,mid-1,key);
else return search(a,mid+1,end,key);
}


int main()
{
int a[8]={5,6,7,8,1,2,3,4};
int key=7;
int k=find_rotation(a,8);
int res;
if(a[0]>key) //the key is in the subpart k+1... n
res=search(a,k+1,7,key);
else // The key is in subpart 0.... k
res=search(a,0,k,key);

printf("the key is found at position %d",res);

return 0;
}</pre>

Comment to the previous quote:

If the array is rotated and sorted, then first the elements in a array will first increase,fall down suddenly to min value and then increase again.

Say 0... i is rotated from the tail. i+1.... n are original first elements of the array.
Compare the key K with A[0].
If K> A[0] then K lies between 0 to i.
If K < A[0] then K lies between i+1 to n.

The point of rotation k is given?

If so, we do binary search within one of the subparts.

If not, we first find out the point of rotation. ... O(log n)
Then we do binary search on the appropriate subpart... O(log n)

Here is the tested working code.
I am doing binary search with complexity of O(nlog n).
Feedback are welcome.

import java.util.*;
class RotatedSearch
{
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter size of the array");
		int n=sc.nextInt();
		int a[]=new int[n];
		System.out.println("Enter the elements of the sorted but rotated array");
		for(int i=0;i<a.length;i++)
		{
			a[i]=sc.nextInt();
		}
		System.out.println("Enter the element to find");
		int k=sc.nextInt();
		n=binarySearch(a,k);
		System.out.println(k+" is present at "+n+"th index of the array");
	}
	static int binarySearch(int[] a,int k)
	{
		if(a.length==0 || a==null)
			return -1;
		int s=0,e=a.length-1;
		while(s<=e)
		{
			int mid=(s+e)/2;
			if(a[mid]==k)
				return mid;
			else if(k>a[mid])
			{
				if(a[s]>a[mid] && a[s]<k)
					e=mid-1;
				else
					s=mid+1;
			}
			else
			{
				if(a[e]<a[mid] && a[e]>k)
					s=mid+1;
				else
					e=mid-1;
			}
		}
		return -1;
	}
}

<pre lang="java" line="1" title="CodeMonkey25313" class="run-this">//package Amazon;

public class RotatedArraySearch {
public static final int[] data = {
6,7,8,9,10,11,12,13,14,1,2,3,4
} ;
public static void main(String[] args) {
// Find staring element
int goal = 6;
RotatedArraySearch rs = new RotatedArraySearch();
boolean found = rs.search(0,data.length-1,goal);
System.out.println(" Key "+goal+" is "+(found ? " found " : "not found"));
//Try to find something not in array
goal = 25;
found = rs.search(0,data.length-1,goal);
System.out.println(" Key "+goal+" is "+(found ? " found " : "not found"));
//Find something in array
goal = 13;
found = rs.search(0,data.length-1,goal);
System.out.println(" Key "+goal+" is "+(found ? " found " : "not found"));

}
public boolean search(int start,int end, int goal) {
int mid =(start+end)/2;
if(start>end) {
return false;
}
if (start == end && data[start] == goal) return true;
if (start == end && data[start] != goal) return false;

if(data[start]<data[end]) {
return this.normalBinarySearch(start, end,goal);
}
else {
//the other part is unsorted.
return (this.search(start,mid,goal) ||
this.search(mid+1,end,goal));
}
}
public boolean normalBinarySearch(int start, int end, int goal) {
int mid = (start+end)/2;
if (start == end && data[mid] != goal) return false;

if (data[mid] == goal) {
return true;
} else if (data[mid] < goal) {
return normalBinarySearch(mid+1, end,goal);
} else {
return normalBinarySearch(start, mid-1,goal);
}
}
}</pre>

#include<iostream>

void binaryrot(int *a,int first,int last,int no,int &found)
{
int mid=(first+last)/2;

printf(" a[%d] is %d no %d\n",mid,a[mid],no);
if(a[mid]==no)
{
found=mid+1;
return;

}
if(first>last)
{
found=-1;
return;
}
if(a[first]<=a[mid])
{
if(no<a[mid] && a[first]<=no)
{
last=mid-1;

}
else

first=mid+1;
}
else
if(no<=a[last] && a[mid]<no)
{
first=mid+1;

}
else

last=mid-1;


binaryrot(a,first,last,no,found);

}



int main()
{
int *a;
int n=0,i=0,found=-1,no;
printf("Enter the number of elements in array\n");
scanf("%d",&n);
a=(int *)malloc(n*sizeof(int));
printf("Enter elements in sorted rotated order \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);

printf("Enter the no. you want to find\n");
scanf("%d",&no);
binaryrot(a,0,n-1,no,found);
if(found == -1)
printf("Element not in list\n");
else
printf("Element at position %d\n",found);

system("PAUSE");
}

We can use a regular binarySearch with a simple modification. here is my code.

instead of passing binSearch(ar, key, start, end) pass,
binSearch(ar,key,start+k,end+k).

public int binSearch(int[] ar, int key, int start, int end)
	{
		if (start > end) return -1;
		if ((start == end) && (ar[start] == key)) return start;
		if ((start == end) && (ar[start] != key)) return -1;

		int mid = (start+end)/2;
		if (ar[mid%5] == key) return mid;
		if(key<ar[mid])
			return binSearch(ar,key,start,mid-1);
		else
			return binSearch(ar,key,mid+1,end);
	}