11.3 Variant 2 - Search a cyclically sorted array

#1

Elements of Programming Interviews - Java

Problem - Search a cyclically sorted array

Variant 2 - Design an O(logn) algorithm for finding the position of an element k in cyclically sorted array.

I have an idea - find the smallest element (which will also give the location of largest element) and use the indices to find the mid and perform binary search. The problem with this approach is figuring out the index of mid and updating it with each iteration.

Any help is appreciated!

0 Likes
#2

What if you were to think of a cyclically sorted array as being a non-cyclically sorted array that’s had all its elements shifted by some offset?

0 Likes
#3

Thank you that helped. I now know how to update the indices!

0 Likes
#4

Happy to help a fellow traveler!

0 Likes