Finding the Smallest number in a rotated sorted array

Binary Search looks for a value in a sorted array. It compares the middle number of the array with the searched value. If the middle number equals the searched value, the position of the middle number is returned. If the middle number is bigger, the left portion of the array is searched using the same logic (binary search), else the right portion of the array is searched using binary search.

Time complexity of the binary search algorithm for finding the smallest number in a sorted rotated array : Log ( N )

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

C++ : Binary search implementation for finding the smallest number in a rotated sorted array in C++11

#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 © 2020, Algotree.org.
All rights reserved.