Searching in c++

SEARCHING IN C++
Presented By: Manoj

LINEAR SEARCH IN C++
• Also known as the sequential search algorithm
• Involves going through a list step by step and comparing each element with the target item
to find its location.
• If a match is found, the algorithm returns the item's position.
• Otherwise, it returns NULL.

Algorithm to implement linear
search in C++
Read the item to be searched by the user.
Compare the search element with the first element in the list.
If they both matches, terminate the function.
Else compare the search element with the next element in

the list.
Repeat steps 3 and 4 until the element to be search is found.

#include<iostream>
using namespace std;
void LinearSearch(int arr[], int len, int item){
for(int i=0;i<len;i++){
if(arr[i] == item){
cout << item << " Found at index : " << i;
return;
}
}
cout << "Not found";
}
int main() {
int arr[] = {10, 5, 15, 21, -3, 7};
// calculating length of array
int len = sizeof(arr)/sizeof(arr[0]);
// item to be searched
int item = 21;
LinearSearch(arr, len, item);
return 0;
Binary Search
Binary Search
 Used to find the given elements from the sorted array by continuously halving the
array and then searching specified elements from a half array.
 And the process goes on till the match is found.
 It works only the sorted data structures.
 The time complexity of the binary search algorithm is O (log n).

Binary search is implemented using following steps
Step 1 - Read the search element from the user.
Step 2 - Find the middle element in the sorted list.
Step 3 - Compare the search element with the middle element in the sorted list.
Step 4 - If both are matched, then display "Given element is found!!!" and terminate the function.
Step 5 - If both are not matched, then check whether the search element is smaller or larger than the middle element.
Step 6 - If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left sublist of the middle element.
Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right sublist of the middle element.
Step 8 - Repeat the same process until we find the search element in the list or until sublist contains only one element.
Step 9 - If that element also doesn't match with the search element, then display "Element is not found in the list!!!" and terminate the
function.
Program
#include<iostream> int main()
using namespace std; {
int binarySearch(int arr[],int left,int right,int searchN) int arr[10]={3,4,5,7,8,9,11,15,16,18};
{ int start=0;
while(left<=right) int endN=9;
{ int searchN=15;
int mid=(right+left)/2; int output= binarySearch(arr,start,endN,searchN);
if(arr[mid]==searchN) if(output== -1)
return mid; {
else if(arr[mid]<searchN) cout<<"Not present";
left=mid+1; }
else
else
{
right=mid-1;
cout<<"present at index "<<output;
} return -1; }
}}
By recursion
#include<iostream>
using namespace std; int main()
int binaryRecu(int arr[],int left,int right,int target) int arr[]={10,20,30,44,55,66,77,88,99,111};
{ int length=sizeof(arr)/sizeof(arr[0]);
if(left>right) int output=binaryRecu(arr,0,length-1,1111);
return -1; if(output==-1)
int mid=(right+left)/2; {
if(arr[mid]==target) cout<<"not found";
return mid; }
else if(arr[mid]<target) else
return binaryRecu(arr,mid+1,right,target); {
else cout<<"Found";
return binaryRecu(arr,left,mid-1,target); }
}
Advantages
 Works faster than linear search.
 It is a simple algorithm.
 Has O(log N) time complexity

Disadvantages
The array needs to be in sorted order for a binary search to work
Difference between binary search and linear search
Difference between binary search and linear search
Linear Search Binary Search
Commonly known as sequential search. Commonly known as half-interval search.
Elements are searched in a sequential manner (one Elements are searched using the divide-and-
by one). conquer approach.
The elements in the array can be in random order. Elements in the array need to be in sorted order.
Linear search is a slow process. Binary search is comparatively faster.
Does not Efficient for larger arrays. Efficient for larger arrays.
The worst-case time complexity is O(n). The worst case time complexity is O(log n).
Thank You

Searching in c++

Uploaded by

Copyright:

Available Formats

Searching in c++

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Searching in c++

Uploaded by

Copyright:

Available Formats

SEARCHING IN C++

Presented By: Manoj

• If a match is found, the algorithm returns the item's position.

• Otherwise, it returns NULL.

If they both matches, terminate the function.

Else compare the search element with the next element in

Repeat steps 3 and 4 until the element to be search is found.

 And the process goes on till the match is found.

 It works only the sorted data structures.

 The time complexity of the binary search algorithm is O (log n).

Step 2 - Find the middle element in the sorted list.

using namespace std; {

int binarySearch(int arr[],int left,int right,int searchN) int arr[10]={3,4,5,7,8,9,11,15,16,18};

while(left<=right) int endN=9;

int mid=(right+left)/2; int output= binarySearch(arr,start,endN,searchN);

if(arr[mid]==searchN) if(output== -1)

else if(arr[mid]<searchN) cout<<"Not present";

using namespace std; int main()

int binaryRecu(int arr[],int left,int right,int target) int arr[]={10,20,30,44,55,66,77,88,99,111};

if(left>right) int output=binaryRecu(arr,0,length-1,1111);

return -1; if(output==-1)

if(arr[mid]==target) cout<<"not found";

else if(arr[mid]<target) else

 Has O(log N) time complexity

Commonly known as sequential search. Commonly known as half-interval search.

Linear search is a slow process. Binary search is comparatively faster.

You might also like