Searching

Searching is the (concept) mechanism of searching an element in the list of da ta stored.

Basically it is used to find the location or to see whether element is available or not in the
list. The application of search occurs when a particular element is required from a set of
stored elements. For example, consider a database of telephone directory. It is required to
find the address when the telephone number is known.
The efficiency of a search tends to depend upon three things.
● The size and organization of the collection of data we are searching

● the search algorithm being used

● The efficiency of the test used to determine if the search is successful.

The popular searching methods are:
● Linear search

● Binary Search

● Fibonacci search
Any search method requires three components. They are,
● Search List: The search list is simply a general term for the collection of elements
that we are searching.
● Key element/ Target element: This is the term we use to refer to the element that
we are searching for. When ever a search is conducted, there are two possible
outcomes:
◦ The element is found in the list ( successful search)
◦ The element is not found ( unsuccessful search)
● Test function (or) operator : These are used to determine how an element in the
search list matched the target element. For numbers ==, !=, >= etc and for strings
strcmp(), strncmp(), strcmpi() etc are used.
Hence, searching is a terchnique of finding accurate location of an element in the given
data list. If the key element is present in the search list then search process is said to be
successful and the search is said to be unsuccessful if the given element does not exist in
the list.
Linear Search
Linear search, also referred as sequential search is the simplest searching technique. In
this, the required element ( key element) is searched linear through out the search list.
The search begins atone end of the list and searches for the required element one by one
until the element is found or till the end of the list is reached. i.e. from the given list, start
the search process by comparing the first element with the key element. If the match is
found, then stop the search. Otherwise compare the second element and so on. Continue
this process till the key element is found or there are no more elements in the list (in this
case the element is not there in the list). The search is said to be successful if the search
element is found and unsuccessful if the search element is not found.
For example, consider the list of 5 elements as, 23 45 67 32 86
● if the key element is 67 then, Start searching by comparing the first element (23)
with the key element(67) . As two elements are not matched, move to second(45)
and so on. The element is found at position 3.
● If the key element is 58 then search linearly through out the list. In this case, the
element is not present in the list.

Algorithm: Linear_Search( A, key,n)

// A is the linear array with n elements and key is the key element
{
i <-- 0; // initialize linear search
while ( a[i] ≠key) do
i <-- i+1;
if ( i=n) then
print ' unsuccessful search'
else
print ' element found at ', i
}
Example:
/* program for linear serach using non- /* program for linear search using recursive
resursive function*/ function */
#include<stdio.h>
#include<conio.h> #include<stdio.h>
int l_search(int[],int,int); #include<conio.h>
void main() int l_search(int[],int,int);
{ void main()
int a[10],i,n,key,x; {
clrscr(); int a[10],i,n,key,x;
printf("Enter Integer Array size :"); clrscr();
scanf("%d",&n); printf("Enter Integer Array size :");
printf("\n Enter elements \n"); scanf("%d",&n);
for(i=0;i<n;i++) printf("\n Enter elements \n");
scanf("%d",&a[i]); for(i=0;i<n;i++)
printf("\n Enter Key element to search :"); scanf("%d",&a[i]);
scanf("%d",&key); printf("\n Enter Key element to search :");
x=l_search(a,key,n); scanf("%d",&key);
if(x==-1) x=l_search(a,key,n-1);
printf("unsuccessful search"); if(x==-1)
else printf("unsuccessful search");
printf("key element found at:%d",x); else
getch(); printf("key element found at:%d",x);
} getch();
int l_search(int a[],int key,int n) }
{ int l_search(int a[],int key,int i)
int i; {
for(i=0;i<n;i++)
{ if(i<0)
if(key==a[i]) return -1;
return i; if(key==a[i])
} return i;
return -1; return l_search(a,key,i-1);
}
}

● The linear search can be applied on sorted or unsorted list of elements i.e. this
method required no ordering of elements in the list that's why it is some times
referred to as ' brute force' method.
● For large size lists, the performance of linear search, how ever makes it a poor
search strategy . The time it takes to perform linear search grows proportationally
with the size of the list.
Analysis:
● If there are N items in the list, then in the 'worst case' (i.e. where there is no key
element in the list or key element is the last element in the list) N comparisons are
 required.
● The 'best case' , in which the first comparison returns a match, it requires a
single(1) comparison.
● The average case roughly requires 'N/1' comparisons to search the element.
Time Complexity Best Case Best Case
O(1) O(N)

Binary Search
The binary search method is a classical method and it is one of the most efficient
searching techniques, which requires the list to be sorted.
To search for an element in the list the binary search procedure splits the list and locates
the moddle element of the list. It is then compared with the search element. If the search
element is matched with the middle element, then the search is complete. Otherwise, the
key element may be in the upperhalf or lower half. If the key element is less than the
middle element, the first part(upperhalf/ left half) of the list is searched else the second
part( lower half/ right half) of the list is searched. The process is continued until the key
element is found or the portion of the sublist to be searched is empty.
In this method,
● the terms ub and lb are used to represent last and first positions of an array. The
mid position is found out as , mid = ( lb+ub)/2.
● Now, compare the key element with the element in the mid position then, any one
the following cases may arise:
case 1: If the key element is equal to the element present in the mid position, then the
search option is complete.
Case 2: if the key element is less than the element present in the mid position, then there
is no need to check elements in the second(right) half of array i.e. right half can be
excluded. Now assign mid-1 to ub.
Case 3: If the key element is greater than the element present in the mid position, then
there is no need to check the elements in the first(left) half of array i.e. left half can be
excluded. Now assign mid+1 to lb.
● This process is executed repeatedly on the non-excluded portion of the array until
the key element is found or if we eliminate all elements from search then we can
say the element is not present in the given list.
Note: Since, in this method, we eliminate elements by half each time, this method is faster
when compared to sequential search.

Algorithm: Binary_Search(A,N,Key)
// A is an array consisting of N elements in ascending order.
// Key is the element to be searched
{
lb <-- 0; ub <-- N-1;
while ( lb<=ub) do
{
mid <-- (lb + ub)/2;
if(key = A[mid]) then
break;
else
if( A[mid] > key) then
ub <-- mid-1;
else
lb <-- mid+1;
}
if(lb>ub)
print ' unsuccessful search';
else
print 'element found at', mid;
}
 /* Program for Binary Search (non - /* Program for Binary Search
recursive) */ (recursive) */
#include<stdio.h>
#include<stdlib.h> #include<stdio.h>
#include<conio.h> #include<conio.h>
int binarysearch(int a[],int key,int low,int int binarysearch(int a[],int key,int low,int
high) high)
{ {
int mid; int mid;
while(low<=high) if (low>high)
{ return -1;
mid=(low+high)/2; else
if(a[mid]==key) {
return mid; mid=(low+high)/2;
if(a[mid]>key) if(a[mid==key)
high=mid-1; return mid;
else else
low=mid+1; if(a[mid]>key)
} return binarysearch(a,key,lb,mid-1);
return -1; else
} return binarysearch(a,key,mid+1,ub);
void main() }
{ }
int a[10],i,n,key,x; void main()
clrscr(); {
printf ("Enter Integer Array size :"); int a[10],i,n,key,x;
scanf("%d",&n); clrscr();
printf("\n Enter elements in Sorted printf ("Enter Integer Array size :");
order\n"); scanf("%d",&n);
for(i=0;i<n;i++) printf("\n Enter elements in Sorted
scanf("%d",&a[i]); order\n");
printf("\n Enter Key element to search :");
scanf("%d",&key); for(i=0;i<n;i++)
x=binarysearch(a,key,0,n-1); scanf("%d",&a[i]);
if(x==-1)
printf("the key element not found"); printf("\n Enter Key element to search :");
else scanf("%d",&key);
printf("the key element found at:%d",x);
getch(); x=binarysearch(a,key,0,n-1);
} if(x==-1)
printf("the key element not found");
else
printf("the key element found at:%d",x);
getch();
}