How to find an element in sorted rotated array?

general
,
1

Given a sorted rotated array, the rotation factor is unknown to you, write a program to find an element in such array in O(log(N)) time and without using any auxiliary space.

Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

     key = 3 //The element to be searched.

Output : 8 //index of 3

PLEASE DON’T SUGGEST ANY APPROACH WITH THE TIME COMPLEXITY HIGHER THAN MENTIONED ABOVE

2

Just google it.

3

@only4

I have already visited the link but I didn’t understand their logic.

4

What do you mean by rotation factor? Is it number of times the array is rotated?

5

if array is [1,2,3] and rotation factor is 1 then resulting array becomes[3,1,2]. We are given rotated array and rotation factor is not known.

clear??

6

Which part of article is troubling you dear?

What they essentially did, is searching for the ‘pivot’ element, or in other words the maximum valued element. Lets say our initial array was-

{1,2,3,4,5,6,7,8,9,10}

After rotation suppose it is-

{4,5,6,7,8,9,10,1,2,3}

Now we can observe that we cannot directly apply binary search on this array as its unsorted. But the key observation which they used was that, look at maximum element/pivot element. Look at the 2 subarrays from {4…10} and{1…3}.

Essentially these 2 subarrays are sorted. We can use binary search in them. Now all we need to decide is in which sub-array the element is lying. That we can decide easily by-

if(k>=arr[0] &&k<=arr[pivot])//pivot stores index of pivot element

Here we simply checked if value of a is in range of [arr[0],arr[pivot]], if yes, then you have to search that array (adjust high accordingly) else we have to look at the other subarray (adjust low accordingly). This can be accomplished with a simple binary search.

In case of any doubt, do contact me :slight_smile:

2 Likes