Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable.
So for example we have sorted array as -
Answer: We can do a binary search with some modified checks.
So lets take arr as array, start be start of the array, end be arr.length-1 and x be the number to find.
Pseudocode:
Program in java
Time Complexity - O(log n)
Thanks.
So for example we have sorted array as -
2,3,6,12, 15, 18.Now suppose the array is rotated k times ( we don't know k), such that array becomes
15, 18,2,3,6,12
Answer: We can do a binary search with some modified checks.
So lets take arr as array, start be start of the array, end be arr.length-1 and x be the number to find.
Pseudocode:
- Find the middle of array
- Select the sorted array part
If a [middle] > a[start] - That means this part of array is sorted and is without rotation. So, we choose array to search as [start] to a[middle] otherwise we choose a[middle] to a[end]. - Now, depending on the array we searched in step 2, we will get the sorted array now. Now if key x lies in range of the array, we will search for the element in that range, otherwise other range.
So, second step helps us get the sorted array on which we can apply binary search.
Program in java
public int rotatedSearch(int[] arr, int start, int end, int x){ if(arr[start] == x){ return start; } else if(arr[end] == x){ return end; } else if(end - start == 1) { return -1; } int middle = (start + end) / 2; //we have no rotation between start and middle, i.e. normal sorted array //if left sub array is sorted if(arr[start] <= arr[middle]){ //if x is less than middle - then x may lie in this part of array if(x <= arr[middle] && x >= arr[start]){ return rotatedSearch(arr, start, middle-1, x); } else { return rotatedSearch(arr, middle+1, end, x); } } //if right sub array is sorted else if(arr[middle] <= arr[end]){ if(x >= arr[middle] && x <= arr[end] ){ return rotatedSearch(arr, middle+1, end, x); } else { return rotatedSearch(arr, start, middle-1, x); } } else { return -1; } }
Time Complexity - O(log n)
Thanks.
0 comments:
Post a Comment