Searching

Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Based on the type of search operation, these algorithms are generally classified into two categories:

● Linear Search

● Binary Search

Linear Search

What is Linear Search?

Linear search is a simple and most basic searching algorithm used to search any element in a list. The basic idea is to search for the required element(key) sequentially from the very beginning to the very last of the list. If the element is found at any position then the position is returned otherwise it shows a message that the element is not present.

The working of Linear search is as follows :

1. Start from the left-most index

2. Check for the key until the end

3. If the element is found return its index

4. If we reach the end of the list then print “Not Found”.

LINEAR SEARCH CODES

/*
Enter the size of the array and the element to be searched for (key-say).
Find whether a certain element “key” is present in the array or not.
If the number “key” is present, then display the array positions where it is present.
*/
#include <bits/stdc++.h>
using namespace std;
// a function to implement the linear search and return a vector containing the positions of the element k.
vector<int> linearSearch(int arr[], int n, int k)
{
vector<int> ans; // It stores the positions of the required elements.
for (int i = 0; i < n; i++)
{
if (arr[i] == k)
ans.push_back(i);
}
return ans;
}
// end of the linear search function
int main()
{
int n; // array size
cout << “Array size: “;
cin >> n;
int arr[n]; // array declaration
cout << “Enter the array elements — → “;
for (int i = 0; i < n; i++)
cin >> arr[i];
int k;
cout << “Enter the element to be searched: “;
cin >> k;
vector<int> ans = linearSearch(arr, n, k);
if (ans.size() == 0) // if the element is not present, vector is empty
cout << “Element was not present”;
else
{
cout << “Element present at positions: “;
for (auto i : ans)
{
cout << i << “ “; // prints the positions
}
}
return 0;
}

Time Complexity: O(n)

Space Complexity: O(1)

Where ’n’ is the number of elements present in the list.

● Worst case scenario: If the element being searched is present at the very last or if it’s not present it takes O(n) time to complete the search.

● Best case scenario: If the element being searched is present at start then it takes only O(1) time to find it.

Let us discuss an example.

Given an array a[5] = { 5, 20 , 31, 24 ,15}

Index → 0 1 2 3 4

We have to find the element, key = 5

In this case search starts from index 0 to index 4. It finds the key at the first index.

Output — -> Element present at positions: 0

Now, We have to find the element, key = 15

In this case search starts from index 0 to index 4. It finds the element at index 4.

Output — -> Element present at positions: 4

Binary Search

What is Binary search?

Binary Search is a sorted array searching algorithm that divides the search interval to half. The goal behind binary search is to make use of the fact that the array is sorted to reduce the time complexity from O(n) to O(logn) keeping the space complexity constant i.e. O(1).

How is it optimized?

When it comes to linear search we have to check every element unlike in binary search. In binary search, we just have to check the middle element and decide later on whether to go to the left or right for further checking.

The basic steps to perform Binary search are:

● Begin with an interval covering the whole array.

● If the value of the search key is less than the item in the middle of the interval, narrow the interval to the left half.

● Otherwise, narrow it to the right half.

● Repeatedly check until the value is found or the interval is empty.

BINARY SEARCH CODES

ITERATIVE APPROACH

#include<iostream>
using namespace std;
//Iterative approach of Binary Search
int binarySearch(int a[],int l,int h,int k)
{
while(l<=h)
{
int mid = l + (h — l)/2;
//Check if k is present at mid
if(a[mid] == k)
return mid;
//If k is greater, check the right half
if(a[mid] < k)
l = mid + 1;
//If k is smaller, check the left half
else
h = mid — 1;
}
//Return -1 if element is not present in the array
return -1;
}
int main()
{
int h,k;
cout<<”Enter size of array: “;
cin>>h;
int a[h];
cout<<”Enter elements: “;
for(int i=0;i<h;i++)
cin>>a[i];
cout<<”Enter element to be searched: “;
cin>>k;
int ans = binarySearch(a,0,h-1,k);
if(ans == -1)
cout<<”Element not present in the array”;
else
cout<<”Element present in the array at index “<<ans;
return 0;
}

RECURSIVE APPROACH

#include<iostream>
using namespace std;
//Recursive approach of Binary Search
int binarySearch(int a[],int l,int h,int k)
{
while(l<=h)
{
int mid = l + (h — l)/2;
//Check if k is present at mid
if(a[mid] == k)
return mid;
//If k is greater, check the right half
if(a[mid] < k)
return binarySearch(a,mid + 1,h,k);
//If k is smaller, check the left half
else
return binarySearch(a,l,mid — 1,k);
}
//Return -1 if element is not present in the array
return -1;
}
int main()
{
int h,k;
cout<<”Enter size of array: “;
cin>>h;
int a[h];
cout<<”Enter elements: “;
for(int i=0;i<h;i++)
cin>>a[i];
cout<<”Enter element to be searched: “;
cin>>k;
int ans = binarySearch(a,0,h-1,k);
if(ans == -1)
cout<<”Element not present in the array”;
else
cout<<”Element present in the array at index “<<ans;
return 0;
}

Time complexity: O(logn)

Space complexity: O(1)

Where ’n’ is the number of elements

● Worst case scenario: target isn’t present in the list or is at the end of the search list takes O(logn) time to find it.

● Best case scenario: target is at the middle of the search list, takes O(1) time to find it.

Let’s Solve an interesting problem

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Using Linear search approach

#include <bits/stdc++.h>
using namespace std;
// function to find the first position
int firstPos(int arr[], int n, int k)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == k)
return i;
}
return -1;
}
// function to find the last position
int lastPos(int arr[], int n, int k)
{
for (int i = n — 1; i >= 0; i — )
{
if (arr[i] == k)
return i;
}
return -1;
}
int main()
{
int n; // array size
cout << “Array size: “;
cin >> n;
int arr[n]; // array declaration
cout << “Enter the array elements — → “;
for (int i = 0; i < n; i++)
cin >> arr[i];
int k;
cout << “Enter the element to be searched: “;
cin >> k;
int first = firstPos(arr, n, k);
int last = lastPos(arr, n, k);
if (first == -1)
cout << “Element not present”;
else
{
cout << “First Occurence: “ << first << endl;
cout << “Last Occurence: “ << last;
}
return 0;
}

Explanation :

Here we have to find the first and the last occurrence of the given element (k) in the given array.

In the function firstpos we find the first occurrence of the k by searching linearly from the very start. Similarly, in the function lastpos we find the last occurrence of the k by searching linearly from the very end. When we find the occurrence we return the index else return -1.

Using binary search approach

#include<stdio.h>
#include<stdlib.h>
int first(int* nums, int numsSize, int target, int l, int h)
{
while ( l <= h)
{
int mid = l + (h — l)/2;
if( (mid == 0 || nums[mid — 1] < target ) && nums[mid] == target )
return mid;
if(target <= nums[mid])
h = mid — 1;
else
l = mid + 1;
}
return -1;
}
int last(int* nums, int numsSize, int target, int l, int h)
{
while (l <= h)
{
int mid = l + (h — l)/2;
if( (mid == numsSize-1|| nums[mid + 1] > target ) && nums[mid] == target )
return mid;
if(target < nums[mid])
h = mid — 1;
else
l = mid + 1;
}
return -1;
}
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
int *arr = (int*)malloc(2*sizeof(int));
int f = -1, l = -1;
f = first(nums,numsSize,target,0, numsSize-1);
l = last(nums,numsSize,target,0, numsSize-1);
arr[0] = f;
arr[1] = l;
*returnSize = 2;
return arr;
}
int main () {
int nums[7]={5,7,7,8,8,10};
int numsSize = 7;
int returnSize;
int *p[2] = searchRange(nums,numsSize,target,&returnSize);
}

Output:- 3 4

Explanation:

Explanation-1.1

Explanation-1.2

Written by Divyansi Mishra, Anoushka Bose, Shashank Jaiswal, Sweekriti Pant