The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list.
the list is rotated by a factor k, so in linear time you find how long is this k. Then you apply a selection shifted by this k in modulo, and each # will cost log (N) with N size of list.
No comments:
Post a Comment