What are Searching Algorithms in data structure – program, example

Searching Algorithms in data structure: is the process of determining the ability of desired element in the given list of elements stored in any order or randomly. Searching operation returns the position of the required element in the list if it is a present otherwise it returns search failures notification. For example in the database library management system we need to search the information about particular book. In Hospital information system we need to search the information about the patient and so on. Searching is divided into two parts: linear or sequential search and binary search.

linear or sequential searching in data structure

This is the simplest searching technique to find out an element in an  unordered list. In this technique ,we access each element of list on by on sequentially and see whether it is a desired element or not .That is the key element is compared with the first element of the list ,if the match is found, then search in successfully and return the position of key. Otherwise next element of the list is compare with key and this process is continue till the key is found or list is completely searched.

Algorithm for sequential searching

• step1: initialize i=0, flag=1
• step2: Repeat step3 for i=0, 1, 2,……..,n-1
• step3: if a[i]==key then, set: flag=0 and display the message: search is successful and key is at location i+1
• step4: if flag ==1, then display : search is failed
• step5: stop

Program for sequential searching

#include<stdio.h>
int main()
{
int a[20],i,x,n;
printf("How many elements?");
scanf("%d",&n);printf("Enter array elements:n");
for(i=0;i<n;++i)
scanf("%d",&a[i]);
printf("nEnter element to search:");
scanf("%d",&x);
for(i=0;i<n;++i)
if(a[i]==x)
break;
if(i<n)
printf("Element found at index %d",i);
else
printf("Element not found");
return 0;
}

output

What is Binary searching Algorithms?

Binary searching algorithms in data structure is an extremely efficient search technique that searches the given item in minimum possible comparison in the  already sorted list of given element. The logic behind this technique is

• first find the middle element of the list.
• compare the mid -element with searched item.

There are three cases:

• If the desired element then search is successful.
• if it is less than desired items in search only the first half of the list.
• greater than Desire element. searched in second half of list. 

In this technique Every time We Are reducing search area .so number of comparisons keep on decreasing. So it is efficient technique when the compared to Linear search.

Algorithm for binary searching

• step1: initialize L=0, H= n-1
• step2: Repeat step 3 and 4 while L<H
• step3: Mid= (L+H/2)
• step4: If key>a [mid] then set L=Mid+1 , Else set H=Mid-1
• step5: if key == a[mid] then search is successful and location= mid+1, Else search failed
• step6: stop.

Example for binary searching

Trace the binary searching algorithms in data structure to search the items :33 and 85 in the following list

6, 13, 14, 25, 33, 43, 51, 53, 64, 72, 84, 93, 95, 96, 97

solution let Lowest=0, Highest=14, key=33

S.N	L	H	Mid=(L+H/2)	Remarks
1 2 3 4	o 0 4 4	14 6 6 5	(0+14)/2=7 (0+6)/2=3 (4+6)/2=5 (4+5)/2=4	key(33)<a[7]=53 key(33)<a[3]=25 key(33)<a[5]=43 key(33)<a[4]=3

Therefore search successful and key (33) is at position.

(mid+1)=(4+1)=5,

Again, L=0, H=14, Key=85(searched for 85)

S.N	L	H	Mid=(L+H/2)	Remarks
1 2 3 4 5	0 8 8 10 11	14 14 10 10 10	(0+14)/2=7 (8+14)/2=11 (8+10)/2=9 (10+10)/2=10 (10+10)/2=10	key(85)<a[7]=53 key(85)<a[11]=93 key(85)<a[9]=72 key(85)<a[10]=84 therefore L>H(i.e. 11>10)

searched failure and key (85) is not present in given list.

Related term

• sorting algorithm,
• Kruskal’s algorithm