Searching in a sorted rotated array is one of the basic problems . In various companies this question is asked how can you search in a sorted rotated array .
Here we have two types of solution.
1. Efficient Solution : In this solution we will use the binary search approach to find the solution. Time complexity for this solution would be O(log n) and auxilary space would be O(1).
class HindiCodingCommunity {
static int search(int arr[],int num){
int low=0,high=arr.length-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]==num){
return mid;
}
if(arr[low]<arr[mid]){
if(num>=arr[low] && num<arr[mid]){
high=mid-1;
}
else{
low=mid+1;
}
}
else{
if(num>arr[mid] && num<=arr[high])
{
low=mid+1;
}
else{
high=mid-1;
}
}
}
return -1;
}
public static void main(String args[])
{
int num[] = {10,20,30,40,5,6};
System.out.println(search(num,6));
}
}
2. Naive Solution : In this solution we will traverse the whole array elements one by one and check whether the given number is present or not. In this solution time complexity will be O(n) while space complexity would be O(1).
class HindiCodingCommunity {
static int search(int arr[],int num){
for(int i=0;i<arr.length;i++){
if(arr[i]==num){
System.out.println(i);
System.exit(0);
}
}
return -1;
}
public static void main(String args[])
{
int num[] = {10,20,30,40,5,6};
System.out.println(search(num,6));
}
}
