Whiplasher
Disciple
Hey Guys,
Had an interview with Expedia yesterday and he threw me a question that I cudnt solve and I was wondering if any of you could come up with the solution.
Given a sorted array for eg 1 3 5 7 9....we use a binary search to find a number in log(n) time...Now assuming the array is shifted to the left by any number of times....ie...lets say 3 places..so that it becomes 7 9 1 3 5.
Now Develop an algortihm to find a number in the sorted shifted array while still retaining the log(n) complexity using a modified version of binary search.
Had an interview with Expedia yesterday and he threw me a question that I cudnt solve and I was wondering if any of you could come up with the solution.
Given a sorted array for eg 1 3 5 7 9....we use a binary search to find a number in log(n) time...Now assuming the array is shifted to the left by any number of times....ie...lets say 3 places..so that it becomes 7 9 1 3 5.
Now Develop an algortihm to find a number in the sorted shifted array while still retaining the log(n) complexity using a modified version of binary search.