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.

Below is an example of rotated sorted array.

Smallest_Number_Rotated_Sorted_Array


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 of finding the smallest number in a sorted rotated array using binary search : Log ( N )

Why is mid calculated as mid = beg + (end-beg)/2 ?

C++ program for finding the smallest number in a rotated sorted array using binary search algorithm.

#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;
    cout << "Position of the smallest : " << S.FindSmallest(arr1) << endl;
    cout << "Position of the smallest : " << S.FindSmallest(arr2) << endl;
    cout << "Position of the smallest : " << S.FindSmallest(arr3) << endl;
    cout << "Position of the smallest : " << S.FindSmallest(arr4) << endl;
    cout << "Position of the smallest : " << S.FindSmallest(arr5) << endl;
    cout << "Position of the smallest : " << S.FindSmallest(arr6) << endl;
    cout << "Position of the smallest : " << S.FindSmallest(arr7) << endl;
    cout << "Position of the smallest : " << S.FindSmallest(arr8) << endl;

    return 0;
}

Output of binary search for finding the position of the smallest number in a rotated sorted array. Implemented in C++11.

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

Copyright (c) 2020, Algotree.org.
All rights reserved.