Problem solving with programming: Finding an element in a circularly sorted array
Given a circularly sorted array, how to search for an element efficiently?
For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.
For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.
Since the array is sorted but rotated, we can expect it to be solved using the binary search technique.
We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.
Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .
We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.
Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .
Read full article from Problem solving with programming: Finding an element in a circularly sorted array
No comments:
Post a Comment