11.5 – Sequential search, Binary search recursive way

by subbu on December 10, 2013

Searching:

Searching is a fundamental requirement in any application, searching is a procedure to retrieve something required from a stored collection. There are different searching techniques used to get the required item from the collection. The most commonly used searching techniques are

  1. Sequential search
  2. Binary search

Sequential search:

It is the simplest searching technique used to search for an element or a record.
Here we start searching for an element from first element to the last element one by one using for i=0,1,2….n-1, where n is the total number of elements.
The function returns the index of element if search is successful otherwise returns -1

int search(int x[],int n,int s)
{
 int i;
 for(i=0;i<n;i++)
   if(x[i]==s)
     return i;       /* on successful search */
 return -1;             /* if element not found */
}

Here x is an array of n elements and we want to search for an item s.

Sequential search implementation in C language:

#include<stdio.h>
int search(int[],int,int);
int main()
{
 int a[50],n,i,s,res;
 printf("How many elements?");
 scanf("%d",&n);
 printf("Enter %d elements:\n",n);
 for(i=0;i<n;i++)
   scanf("%d",&a[i]);
 printf("Enter an element to search:");
 scanf("%d",&s);
 res=search(a,n,s);
 if(res==-1)
   printf("Element not found");
 else
   printf("Element found");
 return 0;
}
int search(int x[],int n,int s)
{
 int i;
 for(i=0;i<n;i++)
   if(x[i]==s)
     return i;
 return -1;
}

Execution:
How many elements?5
Enter 5 elements:
12 45 10 34 44
Enter an element to search:45
Element found

Execution:
How many elements?5
Enter 5 elements:
23 45 76 45 12
Enter an element to search:22
Element not found

Disadvantage of sequential search:

In case of sequential search, we need only one comparison if the required element is existed at the beginning, need two comparisons if the element is the second element and need n comparisons if element is not existed. On average takes (n+1)/2 comparisons to find an element.
It takes more time if a table or a file having thousands of records.

Binary search:

It is efficient than sequential search. Say for example, if we want to search for a word in the dictionary, we don’t search right from the beginning to end because it takes lot of time to find the required word. Rather we randomly open a page and look at the words in that page, we will then decide whether to search back half or front half. We will continue this until we get the required word.

The same technique is used in binary search. It finds the position of the search value within the sorted list. At each stage, the program compares the search value with the middle value of the list. If the key matches, then a matching value has been found so its position is returned. Otherwise, if the search value is less than the middle value, then the program repeats its action on the sub-list to the left of the middle value or, if the input key is greater, on the sub-list to the right. If the remaining list to be searched is reduced to zero, then the value cannot be found in the list and a special not found indication -1 is returned.

Binary search

binary search recursive algorithm

In the procedure bsearch(int x[],int start,int end,int s)

Consider x is an array of n ordered elements and want to search for an item s. start, end are the starting and ending indices of sub array and mid is the middle index of sub array.

1. If there are no elements left to search then return -1

if(start>end)
  return -1;

2. find the middle index of array

mid=(start+end)/2;

3. If the search element and middle element are equal then search is finished and return the mid.

if(s==x[mid])
   return mid;

4. if the search element is less than the middle element then select left sub array to continue search

if(s<x[mid])
  mid=bsearch(x,start,mid-1,s);
return mid;

5. if the search element is greater than the middle element then select right sub array to continue search

if(s>x[mid])
  mid=bsearch(x,mid+1,end,s);
return mid;

Putting all together:

int bsearch(int x[],int start,int end,int s)
{
 int mid;
 if(start>end)
   return -1;
 mid=(start+end)/2;
 if(s==x[mid])
   return mid;
 if(s<x[mid])
   mid=bsearch(x,start,mid-1,s);
 if(s>x[mid])
   mid=bsearch(x,mid+1,end,s);
 return mid;
}

Binary search recursive method implementation in C language:

#include<stdio.h>
int bsearch(int[],int,int,int);
int main()
{
 int a[50],n,i,s,res;
 printf("How many elements?");
 scanf("%d",&n);
 printf("Enter %d elements in order:\n",n);
 for(i=0;i<n;i++)
   scanf("%d",&a[i]);
 printf("Enter an element to search:");
 scanf("%d",&s);
 res=bsearch(a,0,n-1,s);
 if(res==-1)
   printf("Element not found");
 else
   printf("Element found");
 return 0;
}
int bsearch(int x[],int start,int end,int s)
{
 int mid;
 if(start>end)
   return -1;
 mid=(start+end)/2;
 if(s==x[mid])
   return mid;
 if(s<x[mid])
   mid=bsearch(x,start,mid-1,s);
 if(s>x[mid])
   mid=bsearch(x,mid+1,end,s);
 return mid;
}

Execution
How many elements?8
Enter 8 elements:
10 25 37 45 55 62 72 85
Enter an element to search:72
Element found

binary search non recursive method

Here starting and ending indices are reset for every iteration as long as search continue in a loop

int bsearch(int x[],int start,int end,int s)
{
 int mid;
 while(start<=end)
 {
  mid=(start+end)/2;
  if(s==x[mid])
    return mid;             /* if search is successful */
  if(s<x[mid])
    end=mid-1;
  if(s>x[mid])
    start=mid+1;
 }
 return -1;                     /* if search is not successful */
}

Binary search iterative method implementation in C language

#include<stdio.h>
int bsearch(int[],int,int,int);
int main()
{
 int a[50],n,i,s,res;
 printf("How many elements?");
 scanf("%d",&n);
 printf("Enter %d elements in order:\n",n);
 for(i=0;i<n;i++)
   scanf("%d",&a[i]);
 printf("Enter an element to search:");
 scanf("%d",&s);
 res=bsearch(a,0,n-1,s);
 if(res==-1)
   printf("Element not found");
 else
   printf("Element found");
 return 0;
}
int bsearch(int x[],int start,int end,int s)
{
 int mid;
 while(start<=end)
 {
   mid=(start+end)/2;
   if(s==x[mid])
     return mid;
   if(s<x[mid])
     end=mid-1;
   if(s>x[mid])
     start=mid+1;
 }
 return -1;
}

Execution:
How many elements?8
Enter 8 elements:
10 25 37 45 55 62 72 85
Enter an element to search:72
Element found

Previous post:

Next post: