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
0 Comments