# 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:

- 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 intfindRotatedArray(int[] a) {

intn = a.length;

intstart = 0;

intend = n-1;while(start<end){

intmid = start+(end-start)/2;if( a[mid] > a[end]){

start=mid+1;

}else{

end=mid;

}

}

returnstart;

}

OR

private static introtatedBinarySearch1(int[] a) {

intn = a.length;

intstart = 0;

intend = n-1;while(start<end){intmid = start+(end-start)/2;

intprev = (mid+n-1)%n;

intnext = ((mid+1)%n);if(a[mid] < a[prev] && a[mid] < a[next])returnmid;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 intsearch(final int[] A,intB) {//find the minimum element in rotated sorted array

intstart = 0, minIndex = -1, mid;

intn = A.length;

intend = 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 liesend = 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)returnmid;

if(A[mid] < B) {

start = mid + 1;

}else{

end = mid - 1;

}

}

return-1;

}