Binary search on a sorted, but rotated array.

An element in a sorted array can be found in O(log n) time via binary search. But suppose We rotate the sorted array at some pivot unknown to us beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated array in O(log n) time.

Idea:
idea: look at end of array. if the last item is smaller than the key i am searching for and key is less than the mid value, then the array is rotated. this means you need to search for items in the lower part of the array.


i.e. array = (456123) val = 5


else look at the beginning of array. if the first item is bigger than the key i am searching for and key is greater than the mid value, then the array is rotated. this means you need to search for items in the upper part of the array.


i.e. array = (67812345) val = 4


otherwise, the array is not rotated. so, you can proceed with normal binary search.


i.e. array = (12345678) val = any number




Input:
9 2 3 4 5 6 7 8


Output:
Elements in Array:
9 2 3 4 5 6 7 8
Searching for key: 3
Search result: true


Code: