My first intuition was that you could somehow write a binary search with two pointers throwing about half of the array away each time. I ran into issues with this train of thought because there might be duplicates in the array or the array might be all the same number.

My second thought was just do a linear search and if you happen to find the pivot, store it, and make the array sorted. Subsequent calls therefore would result in a binary search.