Search number in a rotated sorted array

Given a rotated sorted array, the goal is to search a number within it using binary search.

Below is an example of rotated sorted array.

Rotated Sorted Array


The algorithm / idea to search the number in a rotated sorted array is as below

Locate (array, beg, end, target)

  • Case a)
    If the array size is 0 the target would not exist in the array.
    If beg > end, it means that the binary search is over and the target does not exist in the array.
    If array[mid] == target, we return the index of the target that has now been found in the array using binary search.

  • Case b)
    From the example in the image it is evident that if ( array[0] <= arr[end] ), the array is already sorted. For a sorted array that has not been rotated, we use a simple binary search to find the number.

  • Case c)
    It is also evident that ( if array[0] <= array[middle] ), the left half of the array is already sorted.
    If the target lies within the sorted left-half of the array we use a simple binary search to find it.
    Else we recursive call Locate (array, mid+1, end, target)

  • Case d)
    Similarly if ( array[mid] <= array[end] ), the right half of the array is already sorted.
    If the target lies within the sorted right-half of the array we use a simple binary search to find it.
    Else we recursive call Locate (array, 0, mid-1, target)


Time complexity of searching a number in a rotated sorted array using binary search : Log ( N )

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

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

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Search{

public:

    int BinSearch(vector<int>& arr, int beg, int end, int target) {

        while (beg <= end) {

            int mid = beg + (end - beg)/2;

            if (arr[mid] == target)
                return mid;
            else if (arr[mid] > target)
                end = mid-1;
            else
                beg = mid+1;
        }
        return -1;
    }

    int Locate(vector<int>& arr, int beg, int end, int target) {

        if (arr.size() == 0 or beg > end)
            return -1;

        int mid = beg + (end - beg)/2;
        int center = arr[mid];

        if (center == target)
            return mid;

        // 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 BinSearch(arr, 0, end, target);
        }

        /* left-half is sorted */
        if (arr[0] <= center) {
            /* target possibly exists in the left-half */
            if (arr[0] <= target and target <= center)
                return BinSearch(arr, 0, mid-1, target);
            /* Target exists in the right half */
            else
                return Locate(arr, mid+1, end, target);
        }
        /* right-half is sorted */
        else if (center <= arr[end]) {
            /* target possibly exists in the right-half */
            if (center <= target and target <= arr[end])
                return BinSearch(arr, mid+1, end, target);
            /* Target exists in the left half */
            else
                return Locate(arr, 0, mid-1, target);
        }
    }
};

int main() {

    Search S;
    vector<int> arr = { 3, 4, 5, 6, 7, 8, -1, 0, 1, 2 };

    cout << "Array : ";
    for (const auto& i : arr) {
         cout << i << " " ;
    } cout << endl;

    while (1) {
        cout << "Search for : ";
        int target;
        cin >> target;
        cout << "Position of " << target << " : " << S.Locate(arr, 0, arr.size()-1, target) << endl;
    }
    return 0;
}

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

Array : 3 4 5 6 7 8 -1 0 1 2 
Search for : 3
Position of 3 : 0
Search for : 4
Position of 4 : 1
Search for : 5
Position of 5 : 2
Search for : 6
Position of 6 : 3
Search for : 7
Position of 7 : 4
Search for : 8
Position of 8 : 5
Search for : 9
Position of 9 : -1
Search for : -1
Position of -1 : 6
Search for : 0
Position of 0 : 7
Search for : 1
Position of 1 : 8
Search for : 2
Position of 2 : 9
Search for : 10
Position of 10 : -1

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