In this post, we will look into search operation in an Array, i.e., how to search an element in an Array, such as:
Searching in an Unsorted Array using Linear Search Searching in a Sorted Array using Linear Search Searching in a Sorted Array using Binary Search
Searching operations in an Unsorted Array using Linear Search In an unsorted array, the search operation can be performed by linear traversal from the first element to the last element, i.e. Linear Search
Coding implementation of the search operation:
C++
#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[] = { 12, 34, 10, 6, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 40;
int position = findElement(arr, n, key);
if (position == -1)
cout << "Element not found";
else
cout << "Element Found at Position: "
<< position + 1;
return 0;
}
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[] = { 12, 34, 10, 6, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 40;
int position = findElement(arr, n, key);
if (position == -1)
printf("Element not found");
else
printf("Element Found at Position: %d",
position + 1);
return 0;
}
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[] = { 12, 34, 10, 6, 40 };
int n = arr.length;
int key = 40;
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));
}
}
Python3
def findElement(arr, n, key):
for i in range(n):
if (arr[i] == key):
return i
return -1
if __name__ == '__main__':
arr = [12, 34, 10, 6, 40]
key = 40
n = len(arr)
index = findElement(arr, n, key)
if index != -1:
print("Element Found at position: " + str(index + 1))
else:
print("Element not found")
C#
using System;
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()
{
int[] arr = { 12, 34, 10, 6, 40 };
int n = arr.Length;
int key = 40;
int position = findElement(arr, n, key);
if (position == -1)
Console.WriteLine("Element not found");
else
Console.WriteLine("Element Found at Position: "
+ (position + 1));
}
}
Javascript
function findElement( arr, n, key)
{
let i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
let arr = [12, 34, 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));
PHP
<?php
function findElement($arr, $n, $key)
{
$i;
for ($i = 0; $i < $n; $i++)
if ($arr[$i] == $key)
return $i;
return -1;
}
$arr = array(12, 34, 10, 6, 40);
$n = sizeof($arr);
$key = 40;
$position = findElement($arr, $n, $key);
if ($position == - 1)
echo("Element not found");
else
echo("Element Found at Position: " . ($position + 1));
?>
Output
Element Found at Position: 5
Time Complexity: O(N) Auxiliary Space: O(1)
Searching in a Sorted Array using Linear Search In a sorted array, the most trivial method for search operation is by using Linear Search .
Below is the implementation of the above approach:
C++
#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[] = { 5, 6, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 10;
int position = findElement(arr, n, key);
if (position == -1)
cout << "Element not found";
else
cout << "Element Found at Position: "
<< position + 1;
return 0;
}
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[] = { 5, 6, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 10;
int position = findElement(arr, n, key);
if (position == -1)
printf("Element not found");
else
printf("Element Found at Position: %d",
position + 1);
return 0;
}
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[] = { 5, 6, 7, 8, 9, 10 };
int n = arr.length;
int key = 10;
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));
}
}
Python3
def findElement(arr, n, key):
for i in range(n):
if (arr[i] == key):
return i
return -1
if __name__ == '__main__':
arr = [5, 6, 7, 8, 9, 10]
key = 10
n = len(arr)
index = findElement(arr, n, key)
if index != -1:
print("Element Found at position: " + str(index + 1))
else:
print("Element not found")
C#
using System;
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()
{
int[] arr = { 5, 6, 7, 8, 9, 10 };
int n = arr.Length;
int key = 10;
int position = findElement(arr, n, key);
if (position == -1)
Console.WriteLine("Element not found");
else
Console.WriteLine("Element Found at Position: "
+ (position + 1));
}
}
Javascript
function findElement( arr, n, key)
{
let i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
return -1;
}
let arr = [5, 6, 7, 8, 9, 10];
let n = arr.length;
let key = 10;
let position = findElement(arr, n, key);
if (position == - 1)
document.write("Element not found");
else
document.write("Element Found at Position: "
+ (position + 1));
PHP
<?php
function findElement($arr, $n, $key)
{
$i;
for ($i = 0; $i < $n; $i++)
if ($arr[$i] == $key)
return $i;
return -1;
}
$arr = array(5, 6, 7, 8, 9, 10);
$n = sizeof($arr);
$key = 10;
$position = findElement($arr, $n, $key);
if ($position == - 1)
echo("Element not found");
else
echo("Element Found at Position: " . ($position + 1));
?>
Output
Element Found at Position: 6
Time Complexity: O(N) Auxiliary Space: O(1)
Searching in a Sorted Array using Binary Search In a sorted array, the search operation can be performed efficiently by using binary search .
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int low, int high, int key)
{
if (high < low)
return -1;
int mid = (low + high) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
int main()
{
int arr[] = { 5, 6, 7, 8, 9, 10 };
int n, key;
n = sizeof(arr) / sizeof(arr[0]);
key = 10;
cout << "Index: " << binarySearch(arr, 0, n - 1, key)
<< endl;
return 0;
}
C
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key)
{
if (high < low)
return -1;
int mid = (low + high) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
int main()
{
int arr[] = { 5, 6, 7, 8, 9, 10 };
int n, key;
n = sizeof(arr) / sizeof(arr[0]);
key = 10;
printf("Index: %d\n", binarySearch(arr, 0, n - 1, key));
return 0;
}
Java
class Main {
static int binarySearch(int arr[], int low, int high,
int key)
{
if (high < low)
return -1;
int mid = (low + high) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
public static void main(String[] args)
{
int arr[] = { 5, 6, 7, 8, 9, 10 };
int n, key;
n = arr.length - 1;
key = 10;
System.out.println("Index: "
+ binarySearch(arr, 0, n, key));
}
}
Python3
def binarySearch(arr, low, high, key):
mid = (low + high)/2
if (key == arr[int(mid)]):
return mid
if (key > arr[int(mid)]):
return binarySearch(arr,
(mid + 1), high, key)
if (key < arr[int(mid)]):
return binarySearch(arr, low, (mid-1), key)
return 0
if __name__ == "__main__":
arr = [5, 6, 7, 8, 9, 10]
n = len(arr)
key = 10
print("Index:", int(binarySearch(arr, 0, n-1, key)))
C#
using System;
public class GFG {
public static int binarySearch(int[] arr, int low,
int high, int key)
{
if (high < low) {
return -1;
}
int mid = (low + high) / 2;
if (key == arr[mid]) {
return mid;
}
if (key > arr[mid]) {
return binarySearch(arr, (mid + 1), high, key);
}
return binarySearch(arr, low, (mid - 1), key);
}
public static void Main(string[] args)
{
int[] arr = new int[] { 5, 6, 7, 8, 9, 10 };
int n, key;
n = arr.Length;
key = 10;
Console.WriteLine(
"Index: " + binarySearch(arr, 0, n - 1, key));
}
}
Javascript
<script>
function binarySearch( arr, low, high, key)
{
if (high < low)
return -1;
let mid = Math.trunc((low + high) / 2);
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
let arr = [ 5, 6, 7, 8, 9, 10 ];
let n, key;
n = arr.length;
key = 10;
document.write( "Index: " + binarySearch(arr, 0, n - 1, key)
+ "</br>");
</script>
PHP
<?php
function binarySearch($arr, $low,
$high, $key)
{
if ($high < $low)
return -1;
$mid = (int)($low + $high) / 2;
if ($key == $arr[(int)$mid])
return $mid;
if ($key > $arr[(int)$mid])
return binarySearch($arr, ($mid + 1),
$high, $key);
return (binarySearch($arr, $low,
($mid -1), $key));
}
$arr = array(5, 6, 7, 8, 9, 10);
$n = count($arr);
$key = 10;
echo "Index: ", (int)binarySearch($arr, 0,
$n-1, $key);
?>
Time Complexity: O(log(n)) Using Binary Search Auxiliary Space: O(log(n)) due to recursive calls, otherwise iterative version uses Auxiliary Space of O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
