Examples:

Input:

arr[]= {5, 1, 2, 3, 4}

num = 1

Output:

Element is found at index: 4


Input:

arr[]= {50, 10, 20, 30, 40}

num = 5

Output:

Element is not Found


#include <bits/stdc++.h>
using namespace std;

int search(int arr[], int l, int r, int num)
{
    if (l > r)
        return -1;

    int mid = (l + r) / 2;
    if (arr[mid] == num)
        return mid;

    // If arr[l..mid] is sorted
    if (arr[l] <= arr[mid])
    {
        // check the whether num lies in first half
        if (num >= arr[l] && num <= arr[mid])
            return search(arr, l, mid - 1, num);

        return search(arr, mid + 1, r, num);
    }
    // arr[mid+1..r] will be sorted
    if (num >= arr[mid] && num <= arr[r])
        return search(arr, mid + 1, r, num);

    return search(arr, l, mid - 1, num);
}

// Main function
int main()
{
    int arr[100], N, num;

    cout << "Enter Number of nums: ";
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }
    cout << "Enter the num to be searched: ";
    cin >> num;

    int index = search(arr, 0, N - 1, num);
    if (index == -1)
    {
        cout << "num is not found";
    }
    else
    {
        cout << "num is found at index: " << index;
    }

    return 0;
}


Output:

Enter Number of nums: 6
6 1 2 3 4 5
Enter the num to be searched: 4
num is found at index: 4