1.1 Search in Rotated Sorted Array

Search in Rotated Sorted Array: Binary Search

Finding elements in the array is a very easy problem, we can use linear search to find elements in O(N) time complexity.

Search in Rotated Sorted Array :

Intuition:

1. Divide the array into two-part, one of them will always be sorted.

2. Now if the sorted array is on the left side then compare the target with the mid and 0 th element to reduce the search space.

3. else if the sorted array is on the right side then compare the target with the mid and n-1 th element to reduce the search space.

public int search1(final int[] A, int B) {
    int n = A.length;
    int low = 0, high = n - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (A[mid] == B) return mid;
        else if (A[0] <= A[mid]) {//left part is sorted
            if (A[0] <= B && B < A[mid]) {
                //B lies on left part
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else {//right part is sorted
            if (A[mid] < B && B <= A[n - 1]) {
                low = mid + 1;//B lies on right part
            } else {
                high = mid - 1;
            }
        }
    }
    
    return -1;
}

Option 2:

Step 1. first find how many times the array is rotated. (You can find an index of minimum element in the array to find how many time arrays are rotated)

private static int findRotatedArray(int[] a) {
    int n = a.length;
    int start = 0;
    int end = n-1;
    while(start<end){
        int mid = start+(end-start)/2;
        if( a[mid] > a[end]){
            start=mid+1;
        }else{
            end=mid;
        }
    }
    return start;
}

OR

private static int rotatedBinarySearch1(int[] a) {
    int n = a.length;
    int start = 0;
    int end = n-1;
    while(start<end){
        int mid = start+(end-start)/2;
        int prev = (mid+n-1)%n;
        int next = ((mid+1)%n);
        if(a[mid] < a[prev] && a[mid] < a[next]) return mid;
        if( a[start] < a[mid] && a[end] <a[mid]){
            start=mid+1;
        }else{
            end=mid-1;
        }
    }
    return -1;
}

step 2. Considering minimum element as the pivot point and check-in which part your element lies

step 3. apply binary search in that part.

FULL CODE:

public static int search(final int[] A, int B) {
    //find the minimum element in rotated sorted array
    int start = 0, minIndex = -1, mid;
    int n = A.length;
    int end = n - 1;
    while (start <= end) {
        mid = start + (end - start) / 2;
        if (A[mid] <= A[n - 1]) {
            minIndex = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    // check in which part our elements lies
    end = n - 1;
    start = 0;
    if (B > A[end]) {
        end = minIndex - 1;
    } else {
        start = minIndex;
    }
    
    //apply binary search
    while (start <= end) {
        mid = start + (end - start) / 2;
        if (A[mid] == B) return mid;
        if (A[mid] < B) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}

Code Link : https://github.com/satishkkk/codingInterview_prep/blob/master/src/com/interviewBitScaler/Lecture5_BinarySearch/rotatedSortedArray.java