In this problem we will try to find the position of an element if exists in a circular sorted array.
To solve this problem we will first try to find the index of the minimum element in the array and then search for the item in the left-part & right-part of the index
Lets take an eg. to solve the problem
Assume first element of the array is
Let
Observing this we can find
Let
There are two cases while comparing A[j] & A[index]
To solve this problem we will first try to find the index of the minimum element in the array and then search for the item in the left-part & right-part of the index
Lets take an eg. to solve the problem
Assume first element of the array is
17
. Then the array will look like this
Let
index
be 10
(position of the min element)
Now if we carefully see the values we will find that values in indices [1, 9] & [10, N] are increasing and min(values[1, 9]) > max(values[10, N])
Observing this we can find
index
using Binary Search (I will use Binary Search using Bit Manipulation) in O(log N) time
Let
j = index + 2^{i}
There are two cases while comparing A[j] & A[index]
- A[index] < A[j]
j is in the left-part (i.e [1, 9] in our example). So, index is incremented to j - A[index] > A[j]
j is in the right-part (i.e [10, N]) & position of min element is ≤ j so we don't update index
item
in left-part & right-part using Binary Search
import java.util.Scanner; class CircularArraySearch { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int[] A = new int[N + 1]; for (int i = 1; i <= N; i++) { A[i] = in.nextInt(); } int trough = 0; for (int i = Integer.highestOneBit(N); i > 0; i >>= 1) { int j = trough | i; if (j <= N && A[Math.max(1, trough)] < A[j]) { trough = j; if (A[trough - 1] > A[trough]) break; } } trough = trough % N + 1; int item = in.nextInt(); int index = find(A, item, trough, N); if (index < 0) { index = find(A, item, 1, trough - 1); } if (index > 0) { System.out.println("Found at " + index); } else { System.out.println("Not found"); } } private static int find(int[] A, int item, int l, int r) { int index = 0; int N = r - l + 1; for (int i = Integer.highestOneBit(N); i > 0; i >>= 1) { int j = index | i; if (j < N && A[j + l] <= item) { index = j; if (A[j + l] == item) break; } } index += l; return item == A[index] ? index : -index; } }
Input
15
23 29 31 37 41 43 47 2 3 5 7 11 13 17 19
47
Output
Found at 7
No comments:
Post a Comment