Binary Search
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;
}

Associate Software Engineer | JP Morgan & Chase

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store