# 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 <= A[mid]) {//left part is sorted            if (A <= 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;}`

Associate Software Engineer | JP Morgan & Chase

## More from satish kathiriya

Associate Software Engineer | JP Morgan & Chase