Program to find element in sorted array of integers that is circulated k number of times in java

Problem Statement:- Write program to find a element in a circulated sorted array in java.

Solution: The given problem can be divided in two parts .First part contains the rotation of sorted array k number of times and second part consists of finding the element in the circulated sorted array .

The problem of array rotation we has already been discussed in our previous post rotate array given number of times .

To solve the second part we need to search element in that already circulated array , for that we can use any search algorithm .The most easiest solution to use linear search in array but its the efficient solution as we need to loop n number of times.

Since our array is already sorted so another solution will be to use binary search algorithm , but our array is circulated so we also need to modify our binary search algorithm .

If you are not aware of binary search then you can learn it in previous post binary search in java .

Here we will solve this problem in three approaches .

1. Using linear search
2. Using recursion
3. Using modified binary search

Note:- In these approaches we will use sorted array after 2 rotations .So in this i will use array rotation program given in post.

1.Using Linear Search :- In this solution we will loop the circulated sorted array and then we will find the element by comparing with array element in each index .

Steps:- 

• rotate sorted array 2 times .
• loop array by the size of array
• compare each array element with search element.
• if element found return true else false.

private static boolean searchElementUsingLoop(int[] ar,int searchElement) {
for (int j : ar) {
if (j == searchElement) {
return true;
}
}
return false;
}

Time Complexity : O(n)  

___________________________________________________________

2.Using recursion :- This solution is same as the linear search since here we will use recursion so we need to define termination conditions.

Steps:-  get the circulated sorted array and search element.

• if index is equal to length of array then return false as whole have checked whole array [terminating condition]
• if array element at given index and search element are equal return true [terminating condition]
• call the same method again with given array , search element and increased index .

private static boolean searchElementUsingRecursion(int[] ar,int searchElement,int index) {
if(index==ar.length)return false;
if(ar[index]==searchElement)return true;
return searchElementUsingRecursion(ar,searchElement,index+1);
}

Time Complexity : O(n)  

___________________________________________________________

3.Using Modified Binary Search :- In this solution we will modify existing binary search algorithm .Since our array is sorted but we have circulated it 2 times .

sorted array : [2,5,6,9,11,14,16,20]

array after 2 rotation : [6,9,11,14,16,20,2,5]

First we will find middle element , then we will decide to search in left or right part of array based on search element .

Steps:- 

• initialize three variables start ,end, mid as start =0,end = array length -1 , mid = (start + end)/2
• start looping array until start <=end 
• compare search element with array[mid] , if equal return true

    now we need to find part of array where element exists as 

• if search element is less than middle element and greater than start element then go to left part
• if search element is greater than middle element and less than end element then go to right part

private static boolean searchElementUsingModifiedBinarySearch(int[] rsar,int searchElem) {
int start=0; int end= rsar.length-1;
int mid;
do {
mid = (start+end)/2;
if (searchElem == rsar[mid]) return true;
else if (rsar[mid] >= rsar[end]) { // right part from middle
if (searchElem < rsar[mid] && searchElem>=rsar[start]) { // go to left part of array
end = mid - 1;
} else {
start = mid+1;
}
}else { // left part from middle
if (searchElem > rsar[mid]) { // go to right part of array
start = mid + 1;
} else {
end = mid - 1;
}
}
} while (start <= end);
return false;
}

Time Complexity : O(log(n))  

_________________________________________________________

Output :- 

search in circulated rotated sorted array

 You can found the full program on below link - find element in circulated sorted array

Thanks .