Find an element in a sorted rotated array without finding pivot (minimum element)

Problem:
Given a sorted integer array with distinct elements which is rotated any number of times and an integer num, find the index of num in the array.
If not found, return -1.

Solution:
1: Initialize start = 0, end = array length - 1
2: Repeat following steps till start less than or equal to end:
(a) Set mid = (start + end)/2
(b) If num == array[mid], return mid.
(c) If array[start…mid] is sorted, i.e. array[start] is less than array[mid]
(i) If array[start] is less than or equal to num is less than or equal to array[mid], set end = mid-1
(ii) Else set start = mid+1
(d) Else If array[mid…end] is sorted, i.e. array[mid] less than or equal to array[end]
(i) If array[mid] is less than or equal to num is less than or equal to array[end], set start = mid+1
(ii) Else set end = mid-1
3: If not found, return -1.

Related Videos:

[tanvi.rastogi]

best explanation for this question...
I used to think it has a very complicated solution till I saw this.

[spk]

Excellent explanation. If you change (d) to array[start] > array[mid] (instead of array[mid] < array[end]), the same solution can be used for case in which there are dups in array. Ofcourse need to add one more condition if array[mid] == array[start] => st++

[IDeserve]

Dear Friends,

If you like our content and would like us to continue making great content for you, please spread the word about IDeserve.
A share/appreciation from you on social network would mean the world to us!


Thanks,
-Team IDeserve.

[IDeserve]

+Erfan Hossain Shoaib
Thanks for your valuable comments! There are many more videos coming soon. Also, you can let us know any interview topic or question of your choice that you would like to see on IDeserve.

[stdafx]

You are just the best. Thank you very much for your work!!1

[ravinjhajharia]

+IDeserve

It will not give the first occurrence of the item(which we has to search) in the case of duplication of some variables, like {0, 9, -3, -1. 0}, in this case, it will return the 5(instead of returning 1) which is 2nd occurrence of expected item.

We can have this condition at the start of function
if(array[start] == array[end] && item == array[start]), then we can return the start index.

[Joyddep]

As always appreciate your explanation!

[goru]

Hi Saurabh,
The example you took above has middle element as pivot; what if it wasn't rotated from the middle of the array? How will this algorithm handle that case?
-Gaurav

[zichenwang]

Thank you. Presentation is great. But the algorithm can not search a target in an array rotated any number of times as your problem statement said. It works when the array rotate at some pivot just one time.

[rajeshdansena]

Thanks man.! I was looking for the explanation like how you do.
.
In this code, I wonder what if the array with size n is rotated by n times(typically a decreasing order array). Then how it is going to behave. I will try but meantime expecting an answer if you see my comment and have done this use case with your code :)

[manikantagandham]

Why don’t you start a online training with a plan. Will be first one to join. 🙏🏻

[meghanabommadi]

no offence but i was listening to this in 2X, thought you said "my name is sorrow" lmao