Array ( [0] => [1] => questions [2] => Strings [3] => Find-element-in-Sorted-rotated-array )
Given an array of integers and value k. Find the element in sorted rotated array.
First line contains the size of the first array. Next line contains the m integers separated by the spaces. Next line contains the value k.
Print the index position else print -1
5 30 40 50 10 20 10
3
9 5 6 7 8 9 10 1 2 3 30
-1
9 5 6 7 8 9 10 1 2 3 3
8
Login to see Discussion
Approach1: Linear Searching
Step-i) Iterate the array by checking every element is equal to it or not.
Step-ii) If it is equal to it, return it directly.
Step-iii) If not found, return -1.
Approach2: Binary Search
Step-i) This approach is to make it sorted by rotating and then applying binary search.
Step-ii) find the peak element, by traversing every element.
Step-iii) Note the index where it is, peak.
Step-iv) If the element is > pivot, Use binary search for the left array,
Step-v) If the element is < pivot, Use binary search for the right array.
Step-vi) Return the index of the output from BinarySearch.
TimeComplexity: O(n)
Space Complexity: O(n)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution