Finding the Smallest number in a rotated sorted array
Given a rotated sorted array, the goal is to find the smallest number within it using binary search.
The algorithm / idea to find the smallest number in a rotated sorted array is as below
FindSmallest (array)
-
Case a) The array is sorted but not rotated.
If ( array [ 0 ] <= arr [ end - 1 ] ), then it means that the array is sorted but not rotated. So we return the first number in the array.
Example: [ 0, 1, 2, 3, 4, 5, 6, 7 ], here arr [ 0 ] <= arr [ 7 ] i.e 0 < 7 so we return 0 as the smallest number. -
Case b) It is a rotated sorted array. The left part of the array is sorted and smallest number exists in the right part.
Else If ( array [ 0 ] <= arr [ mid ] ), where mid is the index of the middle number, the smallest number exist in the right half. So to find the smallest number in the right half that is smaller than arr [ mid ] we use a binary search.
Example: [ 2, 3, 4, 5, 6, 7, 0, 1 ], here arr [ 0 ] <= arr [ 3 ] i.e 2 < 5 so we find the smallest number in the right half i.e in [ 6, 7, 0, 1 ] which is smaller than arr [ mid ] i.e 5. -
Case c) It is a rotated sorted array. The right part of the array is sorted and smallest number exists in the left part.
Else the right part of the array is sorted and the smallest number exists in the left half. So we use a binary search to find the biggest number in the left half. It is evident that the next number after the biggest number of the left half is the smallest number in the array.
Example: [ 6, 7, 0, 1, 2, 3, 4, 5], here the right part of the array is sorted. So we use a binary search to find the biggest number in the left part. [ 6, 7, 0, 1] i.e 7. Once 7 is found we return the next number after 7 i.e 0.
Time complexity : Log ( N ), as we use binary search at the core for solving this problem.
Program for finding the smallest number in a rotated sorted array using binary search algorithm.
def FindSmallest (arr) :
beg = 0
end = len(arr) - 1
mid = beg + int((end - beg)/2)
center = arr[mid]
pos = 0
# Sorted but not rotated.
# 1 2 3 -> 3 1 2 -> 2 3 1 -> 1 2 3
# Note : 2 1 3 is not a valid rotation
if (arr[0] <= arr[end]) :
return pos
# Check if the left half is sorted. If sorted, find the first smaller number on the right
if (arr[0] < center) :
beg = mid
while (beg <= end) :
mid = int(beg + (end - beg)/2)
if (arr[mid] < center) :
pos = mid
end = mid - 1
else :
beg = mid + 1
return pos # 'pos' is the position of the smallest number in the array.
# Right half is sorted. Find the last bigger number on the left
else :
end = mid
while (beg <= end) :
mid = int(beg + (end - beg)/2)
if (arr[mid] > center) :
pos = mid
beg = mid + 1
else :
end = mid - 1
# 'pos' is the position of the last bigger number in the left half of the array.
# So pos+1 is the position of the smallest number in the array.
pos += 1
return pos
def main() :
arr1 = [ 0, 1, 2 ]
arr2 = [ 5, 6, 7, 0, 1, 2 ]
arr3 = [ 2, 3, 4, 5, 6, 7, 0, 1 ]
arr4 = [ 8, 9, 12, 13, 1, 2, 4, 6, 7 ]
arr5 = [ 3, 4, 5, 6, 7, 8, -1, 0, 1, 2 ]
arr6 = [ 7, 8, -1, 0, 1, 2, 3 ]
arr7 = [ 3, 1 ]
arr8 = [ 0, 1 ]
array_list = [ arr1, arr2, arr3, arr4, arr5, arr6, arr7, arr8 ]
for arr in array_list :
print("Array : " + str(arr))
print("Position of the smallest : " + str(FindSmallest(arr)) + "\n")
if __name__ == "__main__" :
main()
Output
Array : [0, 1, 2]
Position of the smallest : 0
Array : [5, 6, 7, 0, 1, 2]
Position of the smallest : 3
Array : [2, 3, 4, 5, 6, 7, 0, 1]
Position of the smallest : 6
Array : [8, 9, 12, 13, 1, 2, 4, 6, 7]
Position of the smallest : 4
Array : [3, 4, 5, 6, 7, 8, -1, 0, 1, 2]
Position of the smallest : 6
Array : [7, 8, -1, 0, 1, 2, 3]
Position of the smallest : 2
Array : [3, 1]
Position of the smallest : 1
Array : [0, 1]
Position of the smallest : 0
#include<iostream>
#include<vector>
using namespace std;
class BinarySearch {
public:
int FindSmallest (vector<int>& arr) {
int beg = 0;
int end = arr.size() - 1;
int mid = beg + (end - beg)/2;
int center = arr[mid];
int pos = 0;
// Sorted but not rotated.
/* 1 2 3 -> 3 1 2 -> 2 3 1 -> 1 2 3
Note : 2 1 3 is not a valid rotation */
if (arr[0] <= arr[end]) {
return pos;
}
// Check if the left half is sorted. If sorted, find the first smaller number on the right
if (arr[0] < center) {
beg = mid;
while (beg <= end) {
mid = beg + (end - beg)/2;
if (arr[mid] < center) {
pos = mid;
end = mid - 1;
} else {
beg = mid + 1;
}
}
return pos; // 'pos' is the position of the smallest number in the array.
}
// Right half is sorted. Find the last bigger number on the left
else {
end = mid;
while (beg <= end) {
mid = beg + (end - beg)/2;
if (arr[mid] > center) {
pos = mid;
beg = mid + 1;
} else {
end = mid - 1;
}
}
/* 'pos' is the position of the last bigger number in the left half of the array.
So pos+1 is the position of the smallest number in the array. */
pos += 1;
return pos;
}
}
};
int main() {
vector<int> arr1 = { 0, 1, 2 };
vector<int> arr2 = { 5, 6, 7, 0, 1, 2 };
vector<int> arr3 = { 2, 3, 4, 5, 6, 7, 0, 1 };
vector<int> arr4 = { 8, 9, 12, 13, 1, 2, 4, 6, 7 };
vector<int> arr5 = { 3, 4, 5, 6, 7, 8, -1, 0, 1, 2 };
vector<int> arr6 = { 7, 8, -1, 0, 1, 2, 3 };
vector<int> arr7 = { 3, 1 };
vector<int> arr8 = { 0, 1 };
BinarySearch S;
vector<vector<int>> array_list = { arr1, arr2, arr3, arr4, arr5, arr6, arr7, arr8 };
for (auto arr : array_list) {
cout << "Position of the smallest : " << S.FindSmallest(arr) << endl;
}
return 0;
}
Output
Position of the smallest : 0
Position of the smallest : 3
Position of the smallest : 6
Position of the smallest : 4
Position of the smallest : 6
Position of the smallest : 2
Position of the smallest : 1
Position of the smallest : 0
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class BinarySearch {
int FindSmallest (int[] arr) {
int beg = 0;
int end = arr.length - 1;
int mid = beg + (end - beg)/2;
int center = arr[mid];
int pos = 0;
// Sorted but not rotated.
/* 1 2 3 -> 3 1 2 -> 2 3 1 -> 1 2 3
Note : 2 1 3 is not a valid rotation */
if (arr[0] <= arr[end]) {
return pos;
}
// Check if the left half is sorted. If sorted, find the first smaller number on the right
if (arr[0] < center) {
beg = mid;
while (beg <= end) {
mid = beg + (end - beg)/2;
if (arr[mid] < center) {
pos = mid;
end = mid - 1;
} else {
beg = mid + 1;
}
}
return pos; // 'pos' is the position of the smallest number in the array.
}
// Right half is sorted. Find the last bigger number on the left
else {
end = mid;
while (beg <= end) {
mid = beg + (end - beg)/2;
if (arr[mid] > center) {
pos = mid;
beg = mid + 1;
} else {
end = mid - 1;
}
}
/* 'pos' is the position of the last bigger number in the left half of the array.
So pos+1 is the position of the smallest number in the array. */
pos += 1;
return pos;
}
}
public static void main (String[] args) {
int[] arr1 = { 0, 1, 2 };
int[] arr2 = { 5, 6, 7, 0, 1, 2 };
int[] arr3 = { 2, 3, 4, 5, 6, 7, 0, 1 };
int[] arr4 = { 8, 9, 12, 13, 1, 2, 4, 6, 7 };
int[] arr5 = { 3, 4, 5, 6, 7, 8, -1, 0, 1, 2 };
int[] arr6 = { 7, 8, -1, 0, 1, 2, 3 };
int[] arr7 = { 3, 1 };
int[] arr8 = { 0, 1 };
BinarySearch S = new BinarySearch();
List<int[]> array_list = new ArrayList<int[]>();
// Add multiple array(s) to a list
Collections.addAll(array_list, arr1, arr2, arr3, arr4, arr5, arr6, arr7, arr8);
for (int[] arr : array_list) {
System.out.println("Position of the smallest : " + S.FindSmallest(arr));
}
}
}
Output
Position of the smallest : 0
Position of the smallest : 3
Position of the smallest : 6
Position of the smallest : 4
Position of the smallest : 6
Position of the smallest : 2
Position of the smallest : 1
Position of the smallest : 0