Searching in array
Searching in Array
Searching in array is a search for an array element based on its value or its index. And it searches an element using the given index or by the value.
Diagramatic Representation
Algorithm
Consider LA is a linear array with N element and K is a positive integer such that K<=N.Following is the algoeithm to find an element with a value of ITEM using sequential search
1.Start
2.Set J=0
3.Repeat steps 4 and 5 while J<N
4.If LA[J] is equal ITEM then goto step 6
5.Set J=J+1
6.Print J,ITEM
7.Stop
Searching in array in Different language
Program in C
#include<stdio.h>
int findElement(int arr[], int n,
int key)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
int main()
{
int arr[] = {2, 3, 10, 6, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 3;
int position = findElement(arr, n, key);
if (position == - 1)
printf("Element not found");
else
printf("Element Found at Position: %d", position + 1 );
return 0;
}
Output
Element Found at Position: 2
Program In CPP
#include<bits/stdc++.h>
using namespace std;
int findElement(int arr[], int n,
int key)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
int main()
{
int arr[] = {2, 3, 10, 6, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 3;
int position = findElement(arr, n, key);
if (position == - 1)
cout << "Element not found";
else
cout << "Element Found at Position: "
<< position + 1;
return 0;
}
Output
Element Found at Position: 2
Program in Java
class Main
{
static int findElement(int arr[], int n,
int key)
{
for (int i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
public static void main(String args[])
{
int arr[] = {2, 3, 10, 6, 40};
int n = arr.length;
int key = 3;
int position = findElement(arr, n, key);
if (position == - 1)
System.out.println("Element not found");
else
System.out.println("Element Found at Position: "
+ (position + 1));
}
}
Output
Element Found at Position: 2
Program in Python
def findElement(arr, n, key):
for i in range (n):
if (arr[i] == key):
return i
return -1
arr = [2, 3, 10, 6, 40]
key = 3
n = len(arr)
index = findElement(arr, n, key)
if index != -1:
print ("element found at position: " + str(index + 1 ))
else:
print ("element not found")
Output
Element Found at Position: 2
Program in Javascript
<script>
function findElement( arr, n, key)
{
let i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
let arr = [2, 3, 10, 6, 40];
let n = arr.length;
let key = 40;
let position = findElement(arr, n, key);
if (position == - 1)
document.write("Element not found");
else
document.write("Element Found at Position: "
+ (position + 1));
</script>
Output
Element Found at position: 2
Time Complexity Analysis Searching for an element in an array
Worst Case – O(N)
If the key present in arr[N – 1] (last index), the for loop will work for N times.
Where N is the number of elements in the array.
Hence the time complexity will be O(N).
Best Case – O(1)
If the key is present in arr[0], the for loop will break after its first iteration.
So the time complexity will be O(1)
Also, read the various Array Operation