Searching in Sorted Circular Array

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 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 + 2i
There are two cases while comparing A[j] & A[index]

1. A[index] < A[j]
   j is in the left-part (i.e [1, 9] in our example). So, index is incremented to j
2. 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

After this operation index will point to the max element in left-part. Hence, index + 1 gives the position of min element in A. And atlast we search for the 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