An element in a sorted array can be found in `O(log n)`

time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, `[ 1, 2, 3, 4, 5 ]`

might become `[ 3, 4, 5, 1, 2 ]`

. Devise a way to find an element in the rotated array in `O(log n)`

time.

For inputs `arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}`

and `key = 3`

the correct answer is `8`

.

For inputs `arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}`

and `key = 30`

the correct answer is `-1`

.

For Inputs `arr[] = {30, 40, 50, 10, 20}`

and `key = 10`

the correct answer is `3`

.

You are not signed in. You can only run/submit code after signing in. Create your free Codela account now!