On Searches

• Find whether an user-given element exists in a cyclically sorted array [ For eg, say find whether 108 exists in a cyclically sorted array 67,89,109,4,26,33,45,55 with indices from 1 to 8 ] .

• Suppose you have an infinite sequence of integers ( lets say some kind of streaming data ) all of which arrive in sorted order in a buffer area ( in the form of an array ) . How do you find a particular element ? Note that you can't use a binary search since the size of the array is not known
  

• Suppose you know beforehand that an array has sorted integers in such a way that they are almost uniformly distributed. How do you find the existence of a particular element ?

Answers(?)

• Two binary searches , one to find the smallest element and hence start of the sorted array and another to find the required element

• Use the doubling search . Search elements at positions 2,4,8,16,32, etc .Once the range is found, binary search within the range . O(log i) + O(log j) where 'i' is the index at which you stop doubling search and 'j' is the number of elements within the range
  

• Use the interpolation search . Rather than dividing the interval by half everytime, try to guess the neighbourhood of the element of interest by finding out the interval of separation between successive elements ( works well with uniformly distributed elements ). [Reference].Supposed be of O(loglogn) on an average ( Proof ? )