Algo Ramblings: Find element in bitonic array
Given an array which is monotonically increasing and then decreasing . Write an algorithm to search for a given element. Expected algorithm O(Log n)
An array of number is bitonic if it consists of a strictly increasing sequence followed by a strictly decreasing sequence. We can solve the problem in 3logN comparisons by finding the maximum in the array and then doing two binary searches, one on the increasing and one on the decreasing sequence. The maximum can be found in Log N comparisons using binary search. Each step compares two adjacent numbers A[i] and A[i+1]. If hey are equal, they are both maximum. If A[i] is smaller, we restrict the search to indices at most i, if A[i+1] is bigger, we restrict the search to indices greater than i.
Read full article from Algo Ramblings: Find element in bitonic array
No comments:
Post a Comment