Search for an element in the sorted and rotated array in C/C++/Python/Java
In C:
First, we take an array and define its mid, lower, and upper limit. Then we have different conditions to check, whether the element lies in between the lower and middle or between the middle and upper.
The element to be searched is taken from the user and if it is found then it will return its index or it will print not found.
#include <stdio.h>
int search(int arr[ ], int l, int h, int e)
{ int mid = (l + h) / 2;
if (l > h)
return -1;
if (arr[mid] == e)
return mid;
if (arr[l] <= arr[mid]) {
if (e >= arr[l] && e <= arr[mid])
return search(arr, l, mid - 1, e);
return search(arr, mid + 1, h, e);
}
if (e >= arr[mid] && e <= arr[h])
return search(arr, mid + 1, h, e);
return search(arr, l, mid - 1, e);
}
int main()
{int i;
int arr[] = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int e;
printf("enter the number to be searched ");
scanf("%d",&e);
i= search(arr, 0, n - 1, e);
if (i != -1)
printf("Index: %d\n", i);
else
printf("element not found");
return 0;
}
The output:
Enter the number to be searched: 7
Index 3
In C++:
The only difference between C and C++ is the difference between their input and output statements. The procedure to find the element is the same first, we take an array and define its mid, lower, and upper limit. Then we have different conditions to check, whether the element lies in between the lower and middle or between the middle and upper.
The element to be searched is taken from the user and if it is found then it will return its index or it will print not found.
#include <bits/stdc++.h>
using namespace std;
int search(int arr[], int l, int h, int e)
{int mid = (l + h) / 2;
if (l > h)
return -1;
if (arr[mid] == e)
return mid;
if (arr[l] <= arr[mid])
{
if (e >= arr[l] && e <= arr[mid])
return search(arr, l, mid - 1, e);
return search(arr, mid + 1, h, e);
}
if (e >= arr[mid] && e <= arr[h])
return search(arr, mid + 1, h, e);
return search(arr, l, mid - 1, e);
}
int main()
{ int e;
int arr[] = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Type a number: ";
cin >> e; // Get user input from the keyboard
int i = search(arr, 0, n - 1, e);
if (i != -1)
cout << "Index: " << i << endl;
else
cout << "element not found";
}
The output :
Type a number: 10
Element not found
In Python:
In python, we have a function to search an element in the similar way we did to find the middle, upper, and lower limit and search in between them. If the element exists, then it will give the index, or it will print the element not found.
def search (arr, l, h, e):
if l > h:
return -1
mid = (l + h) // 2
if arr[mid] == e:
return mid
if arr[l] <= arr[mid]:
if e >= arr[l] and e <= arr[mid]:
return search(arr, l, mid-1, e)
return search(arr, mid + 1, h, e)
if e >= arr[mid] and e <= arr[h]:
return search(arr, mid + 1, h, e)
return search(arr, l, mid-1, e)
arr = [4, 5, 6, 7, 8, 9, 1, 2, 3]
e=int(input("enter a number"))
i = search(arr, 0, len(arr)-1, e)
if i != -1:
print ("Index: % d"% i)
else:
print ("element not found")
The output :
Enter a number 4
Index 0
In java :
Using Module Scanner we scan for an element, using a function we search for an element in between the array
import java.util.Scanner;
class Main {
static int search(int arr[], int l, int h, int e)
{int mid = (l + h) / 2;
if (l > h)
return -1;
if (arr[mid] == e)
return mid;
if (arr[l] <= arr[mid]) {
if (e >= arr[l] && e <= arr[mid])
return search(arr, l, mid - 1, e);
return search(arr, mid + 1, h, e);
}
if (e >= arr[mid] && e <= arr[h])
return search(arr, mid + 1, h, e);
return search(arr, l, mid - 1, e);
}
public static void main(String args[])
{
int arr[] = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
int n = arr.length;
Scanner sc= new Scanner(System.in);
System.out.print("Enter the number- ");
int e= sc.nextInt();
int i = search(arr, 0, n - 1, e);
if (i != -1)
System.out.println("Index: " + i);
else
System.out.println("element not found");
}
}
The output:
Enter the number- 6
Index 2
Time complexity: O(log n): Binary Search requires a log of n comparisons to find the element in an array. So time complexity is O(log n).
Space Complexity: O(1), as no extra space is required.