Given an array arr[] of n elements, write a function to recursively search a given element x in arr[].
Illustration:
Input : arr[] = {25, 60, 18, 3, 10}
Output : Element to be searched : 3
Input : arr[] = {10,20,30,24,15,40}
Output : -1
For x = 35
Element x is not present in arr[]
Procedure:
The idea is to search the element from both the sides of array recursively. If the element that needs to searched matches with the leftmost element of the left boundary, or it matches with the rightmost element of the right boundary, directly return the position of the element, else recur for the remaining array to search for the element with the value same as x.
Example
Java
// Java Program to Search an element in an Array Recursively// Main classpublic class GFG { // Method 1 // Recursive method to search for an element and // its index in the array static int recursiveSearch(int arr[], int l, int r, int x) { // if r<l,it means that element is not present in // the array if (r < l) return -1; if (arr[l] == x) return l; if (arr[r] == x) return r; // Since element has not found on both left most and // rightmost boundary,ie at l and r, now recursive the // array to find position of x. return recursiveSearch(arr, l + 1, r - 1, x); } // Method 2 // Main driver method public static void main(String[] args) { // Element to be searched for // Custom input number int x = 3; // Declaring and initializing the integer array int arr[] = new int[] { 25, 60, 18, 3, 10 }; // Calling the above recursive method method to // search for the element in the array // Recursive function is called over array to // get the index of the element present in an array int index = recursiveSearch(arr, 0, arr.length - 1, x); // If index is found means element exists if (index != -1) // Print the element and its index System.out.println("Element " + x + " is present at index " + index); // If we hit else case means // element is not present in the array else // Simply display the corresponding element // is not present System.out.println("Element " + x + " is not present"); }} |
Output
Element 3 is present at index 3
Time complexity: O(N2) where N is size of input array
Auxiliary Space : O(N)
