Finding the Smallest number in a rotated sorted array

Smallest_Number_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.

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


C++ : 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

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) 2019-2021, Algotree.org.
All rights reserved.