View Discussion
Improve Article
Save Article
ReadDiscussView Discussion
Improve Article
Save Article
Given an unsorted array and an element x, search x in the given array. Write recursive C code for this. If the element is not present, return
-1.
Approach : The idea is to compare x with the last element in arr[]. If the element is found at the last position, return it. Else recur searchElement() for remaining array and element x.
C++
#include <iostream>
using
namespace
std;
int
searchElement(
int
arr[],
int
size,
int
x) {
size--;
if
(size < 0) {
return
-1;
}
if
(arr[size] == x) {
return
size;
}
return
searchElement(arr, size, x);
}
int
main() {
int
arr[] = {17, 15, 11, 8, 13, 19};
int
size =
sizeof
(arr) /
sizeof
(arr[0]);
int
x = 11;
int
idx = searchElement(arr, size, x);
if
(idx != -1)
cout <<
"Element "
<< x <<
" is present at index "
<<idx;
else
cout <<
"Element "
<< x <<
" is not present in the array"
;
return
0;
}
C
#include <stdio.h>
int
elmntSrch(
int
arr[],
int
size,
int
x) {
int
rec;
size--;
if
(size >= 0) {
if
(arr[size] == x)
return
size;
else
rec = elmntSrch(arr, size, x);
}
else
return
-1;
return
rec;
}
int
main(
void
) {
int
arr[] = {12, 34, 54, 2, 3};
int
size =
sizeof
(arr) /
sizeof
(arr[0]);
int
x = 3;
int
indx;
indx = elmntSrch(arr, size, x);
if
(indx != -1)
printf
(
"Element %d is present at index %d"
, x, indx);
else
printf
(
"Element %d is not present"
, x);
return
0;
}
Java
class
Test
{
static
int
arr[] = {
12
,
34
,
54
,
2
,
3
};
static
int
recSearch(
int
arr[],
int
l,
int
r,
int
x)
{
if
(r < l)
return
-
1
;
if
(arr[l] == x)
return
l;
if
(arr[r] == x)
return
r;
return
recSearch(arr, l+
1
, r-
1
, x);
}
public
static
void
main(String[] args)
{
int
x =
3
;
int
index = recSearch(arr,
0
, arr.length-
1
, x);
if
(index != -
1
)
System.out.println(
"Element "
+ x +
" is present at index "
+
index);
else
System.out.println(
"Element "
+ x +
" is not present"
);
}
}
Python3
def
recSearch( arr, l, r, x):
if
r < l:
return
-
1
if
arr[l]
=
=
x:
return
l
if
arr[r]
=
=
x:
return
r
return
recSearch(arr, l
+
1
, r
-
1
, x)
arr
=
[
12
,
34
,
54
,
2
,
3
]
n
=
len
(arr)
x
=
3
index
=
recSearch(arr,
0
, n
-
1
, x)
if
index !
=
-
1
:
print
(
"Element"
, x,
"is present at index %d"
%
(index))
else
:
print
(
"Element %d is not present"
%
(x))
C#
using
System;
static
class
Test
{
static
int
[]arr = {12, 34, 54, 2, 3};
static
int
recSearch(
int
[]arr,
int
l,
int
r,
int
x)
{
if
(r < l)
return
-1;
if
(arr[l] == x)
return
l;
if
(arr[r] == x)
return
r;
return
recSearch(arr, l+1, r-1, x);
}
public
static
void
Main(String[] args)
{
int
x = 3;
int
index = recSearch(arr, 0, arr.Length-1, x);
if
(index != -1)
Console.Write(
"Element "
+ x +
" is present at index "
+ index);
else
Console.Write(
"Element "
+ x +
" is not present"
);
}
}
PHP
<?php
function
recSearch(
$arr
, int
$l
,
int
$r
, int
$x
)
{
if
(
$r
<
$l
)
return
-1;
if
(
$arr
[
$l
] ==
$x
)
return
$l
;
if
(
$arr
[
$r
] ==
$x
)
return
$r
;
return
recSearch(
$arr
,
$l
+1,
$r
-1,
$x
);
}
$arr
=
array
(12, 34, 54, 2, 3);
$i
;
$n
=
count
(
$arr
);
$x
= 3;
$index
= recSearch(
$arr
, 0,
$n
- 1,
$x
);
if
(
$index
!= -1)
echo
"Element"
,
" "
,
$x
,
" "
,
"is present at index "
,
$index
;
else
echo
"Element is not present"
,
$x
;
?>
Javascript
<script>
function
recSearch(arr, l, r, x)
{
if
(r < l)
return
-1;
if
(arr[l] == x)
return
l;
if
(arr[r] == x)
return
r;
return
recSearch(arr, l+1, r-1, x);
}
let arr = [12, 34, 54, 2, 3];
let i;
let n = arr.length;
let x = 23;
let index = recSearch(arr, 0, n - 1, x);
if
(index != -1){
document.write(`Element ${x} is present at index ${index}`);
}
else
{
document.write(
"Element is not present "
+ x);
}
</script>
Output
Element 11 is present at index 2
Explanation
We iterate through the array from the end by decrementing the size variable and recursively calling the function searchElement(). If the size variable becomes less
than zero it means the element is not present in the array and we return -1. If a match is found, we return the size variable which is the index of the found element. This process is repeated until a value is returned to main().
It is important to note that if there are duplicate elements in the array, the index of the last matched element will be returned since we are (recursively) iterating the array from the end.
Time Complexity: O(N), where N is the size of the
given array.
Auxiliary Space: O(1)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above