Searching Techniques in Data structure

Searching:

It is a process to find an element from a set of elements stored in order or randomly. There are mainly two types of searching techniques:
1. Sequential Search
2. Binary Search

Sequential Search:

Sequential Searching an element linearly. This can be in an array or a linked list. The array or linked list may be in sorted or unsorted order. We need to start the search from the beginning and scan the elements one by one until the end of an array or linked list. For a successful search, it returns the location of the element, otherwise, it returns the failure notification.

Algorithm for Sequential Search in Array:

Algorithm fnSequentialSearch_Array(arrData, item, n)
{
for(i=0; i<=n-1; i++)
{
if(arrData[i]==item)
{
return i;
break;
}
}
return -1;
} // End of Algorithm

Algorithm for Sequential Search in Linked List:

Algorithm fnSequentialSearch_LinkedList(ptrStart, item)
{
SLLNode *ptrTemp;
ptrTemp=ptrStart;
iPosition=1;
while(ptrTemp!=NULL)
{
if(ptrTemp->iData==item)
return iPosition;
ptrTemp=ptrTemp->ptrNext;
iPosition=iPosition+1;
}
return -1;
} // End of Algorithm

Binary Search:

Binary Search is performed over a sorted array of elements.

Binary Search Technique:
1. At first, find the middle element of the array.
2. Compare the middle element with the item.
3. There are three cases:

    • i. If it is the desired element then the search is successful.

 

    • ii. If it is less than the desired element then search only the first half of the array.

 

    iii. If it is greater than the desired element search in the second half of the array.

Algorithm for Non-Recursive Binary Search:

Algorithm fnBinarySearch_NonRecursive(arrData, low, high, item)
{
while(low>high)
{
mid=(low+high)/2;
if(item==arrData[mid])
return mid;
else if(item<arrData[mid])
high=mid-1;
else
low=mid+1;
}
return -1;
} // End of Algorithm

Algorithm for Recursive Binary Search:

Algorithm fnBinarySearch_Recursive(arrData, low, high, item)
{
if(low>high)
return -1;
else
{
mid=(low+high)/2;
if(item==arrData[mid])
return mid;
else if(item<arrData[mid])
fnBinarySearch_Recursive(arrData, low, mid-1, item);
else
fnBinarySearch_Recursive(arrData, mid+1, high, item);
}
} // End of Algorithm