Category Archives: Search Algorithms

Search Algorithms

Interpolation Search Algorithm

What Is Interpolation Search Algorithm?

Interpolation search is an efficient search algorithm for finding an item in a sorted list of items. Interpolation search algorithm works only on a sorted list of elements. In order to search an element using interpolation search algorithm, we must ensure that the list is sorted and evenly distributed. Interpolation search algorithm is a combination of both binary search and linear search algorithms. Interpolation search, also called as extrapolation search.

Interpolation Search Program In C

#include <stdio.h>
int interpolation_search(int a[], int low, int high, int val)
{
	int mid;
	while(low <= high)
	{
		mid=low + (high-low) * ((val - a[low]) / (a[high] - a[low]));
		
		if(val == a[mid])
		return mid;

		if(val < a[mid]){
			high = mid - 1;
		}
		else{
			low = mid + 1;
		}
		
	}
	return -1;
}

int main()
{
    int a[30], ctr, n, val, loc;
    
    printf("Enter number of elements in array:\n");
    scanf("%d", &n);

    printf("Enter %d integer numbers in ascending order:\n", n);
    for (ctr = 0; ctr < n; ctr++)
    scanf("%d", &a[ctr]);
    
    printf("Enter a number to search:\n");
    scanf("%d", &val);

	loc = interpolation_search(a, 0, n-1, val);
	if(loc == -1)
	printf("%d is not present in the list.\n", val);
	else
	printf("%d is found at location %d.\n", val,loc+1);
	
	return 0;
}

#include <stdio.h>

int interpolation_search(int a[], int low, int high, int val)

{

int mid;

while(low <= high)

{

mid=low + (high-low) * ((val - a[low]) / (a[high] - a[low]));

if(val == a[mid])

return mid;

if(val < a[mid]){

high = mid - 1;

}

else{

low = mid + 1;

}

return -1;

}

int main()

{

int a[30], ctr, n, val, loc;

printf("Enter number of elements in array:\n");

scanf("%d", &n);

printf("Enter %d integer numbers in ascending order:\n", n);

for (ctr = 0; ctr < n; ctr++)

scanf("%d", &a[ctr]);

printf("Enter a number to search:\n");

scanf("%d", &val);

loc = interpolation_search(a, 0, n-1, val);

if(loc == -1)

printf("%d is not present in the list.\n", val);

else

printf("%d is found at location %d.\n", val,loc+1);

return 0;

}

Output:-

Jump Search Algorithm

Jump Search Program In C

#include <stdio.h>
#include <math.h>
int jump_search(int arr[], int search);
int n;
int main()
{
  
   int arr[30],i,search,loc;
   printf("Enter the number of elements: \n");
   scanf("%d",&n);
   printf("Enter %d integer numbers in ascending order:\n", n);
   for(i=0;i<n;i++)
   {
         scanf("%d",&arr[i]);
   }
      printf("Enter a number to search:\n");
      scanf("%d",&search);
      loc=jump_search(arr, search);
      if(loc==-1)
      {
        printf("%d is not present in the list.\n", search);
      }
      else
      {
        printf("%d is found at location %d.\n", search,loc);
      }
      return 0;
}
int jump_search(int arr[], int search){
   int jump_step,prev=0;
   jump_step=floor(sqrt(n));
 
   while(arr[prev]<search){
       if(arr[jump_step]>search || jump_step>=n){
            break;
       }
       else{
                prev=jump_step;
                jump_step=jump_step+floor(sqrt(n));
       }
   }
 
   while(arr[prev]<search){
        prev++;
   }
 
   if(arr[prev]==search){
        return prev+1;
   }
   else{
        return -1;
   }
 
}

#include <stdio.h>

#include <math.h>

int jump_search(int arr[], int search);

int n;

int main()

{

int arr[30],i,search,loc;

printf("Enter the number of elements: \n");

scanf("%d",&n);

printf("Enter %d integer numbers in ascending order:\n", n);

for(i=0;i<n;i++)

{

scanf("%d",&arr[i]);

}

printf("Enter a number to search:\n");

scanf("%d",&search);

loc=jump_search(arr, search);

if(loc==-1)

{

printf("%d is not present in the list.\n", search);

}

else

{

printf("%d is found at location %d.\n", search,loc);

}

return 0;

}

int jump_search(int arr[], int search){

int jump_step,prev=0;

jump_step=floor(sqrt(n));

while(arr[prev]<search){

if(arr[jump_step]>search || jump_step>=n){

break;

}

else{

prev=jump_step;

jump_step=jump_step+floor(sqrt(n));

}

while(arr[prev]<search){

prev++;

}

if(arr[prev]==search){

return prev+1;

}

else{

return -1;

}

Output:-

Binary Search Algorithm

What Is Binary Search Algorithm?

Binary search is one of the commonly used search algorithm in data structure. The Binary search is an efficient search algorithm for finding an item in a sorted list of items. Binary search algorithm works only on a sorted list of elements. In order to search an element using binary search algorithm, we must ensure that the list is sorted. When binary search is performed with a sorted list, the number of iterations can be reduced significantly.

How Binary Search Algorithm Works

Binary search algorithm is based on divide and conquer approach. In Binary search, an item is searched by comparing middle most element of the sorted list. If the search item is matched with the middle element of the list, then it returns the index of matched element. Otherwise, we check whether the given search item is smaller or larger than the middle element of the list. If the search item is smaller, then we will repeat this search process in the left sub-list to find the item. If the search item is greater, then we will repeat this search process in the right sub-list to find the item.

At each step, we have reduced search space to find the target value because the list is sorted, We repeat this process until we find the search item in the list or we left with a sub-list consisting of a single element. And if the search item is not found in list then the “Search Item not found.” result is displayed.

Binary Search Program In C

#include <stdio.h>

int main()
{
  int a[100], search, ctr, n, first, last, middle;

  printf("Enter number of elements in array:\n");
  scanf("%d", &n);
 
  printf("Enter %d integer numbers:\n", n);
 
  for (ctr = 0; ctr < n; ctr++)
    scanf("%d", &a[ctr]);
 
  printf("Enter a number to search:\n");
  scanf("%d", &search);

  first = 0;
  last = n - 1;
  middle = (first+last)/2;

  while (first <= last) {
    if (a[middle] < search)
      first = middle + 1;
    else if (a[middle] == search) {
      printf("%d is found at location %d.\n", search, middle+1);
      break;
    }
    else
      last = middle - 1;

    middle = (first + last)/2;
  }
  if (first > last)
    printf("%d is not present in the list.\n", search);

  return 0;
}

#include <stdio.h>

int main()

{

int a[100], search, ctr, n, first, last, middle;

printf("Enter number of elements in array:\n");

scanf("%d", &n);

printf("Enter %d integer numbers:\n", n);

for (ctr = 0; ctr < n; ctr++)

scanf("%d", &a[ctr]);

printf("Enter a number to search:\n");

scanf("%d", &search);

first = 0;

last = n - 1;

middle = (first+last)/2;

while (first <= last) {

if (a[middle] < search)

first = middle + 1;

else if (a[middle] == search) {

printf("%d is found at location %d.\n", search, middle+1);

break;

}

else

last = middle - 1;

middle = (first + last)/2;

}

if (first > last)

printf("%d is not present in the list.\n", search);

return 0;

}

Output:-

Linear Search Algorithm

What Is Linear Search Algorithm?

Linear search algorithm is a simple search algorithm. Linear search algorithm is also known as sequential search algorithm. In this type of search algorithms, we simply search for an element or value in a given array by traversing the all array elements sequentially from the beginning of the array till the desired element or value is found. In Linear search, each array element is matched to find the desired search element. If a match found then location of the matched item is returned else it returns NULL.

Linear Search Program In C

#include <stdio.h>

int main()
{
  int a[100], search, ctr, n;

  printf("Enter number of elements in array:\n");
  scanf("%d", &n);

  printf("Enter %d integer numbers:\n", n);

  for (ctr = 0; ctr < n; ctr++)
    scanf("%d", &a[ctr]);

  printf("Enter a number to search:\n");
  scanf("%d", &search);

  for (ctr = 0; ctr < n; ctr++)
  {
    if (a[ctr] == search)    
    {
      printf("%d is found at location %d.\n", search, ctr+1);
      break;
    }
  }
  if (ctr == n)
    printf("%d is not found in the array.\n", search);

  return 0;
}

#include <stdio.h>

int main()

{

int a[100], search, ctr, n;

printf("Enter number of elements in array:\n");

scanf("%d", &n);

printf("Enter %d integer numbers:\n", n);

for (ctr = 0; ctr < n; ctr++)

scanf("%d", &a[ctr]);

printf("Enter a number to search:\n");

scanf("%d", &search);

for (ctr = 0; ctr < n; ctr++)

{

if (a[ctr] == search)

{

printf("%d is found at location %d.\n", search, ctr+1);

break;

}

if (ctr == n)

printf("%d is not found in the array.\n", search);

return 0;

}

Output:-

Differences

Linked List

Queue

Search Algorithms

Sorting Algorithms

More Data Structure Tutorial

Learn

ABOUT PAGES

Category Archives: Search Algorithms

Interpolation Search Algorithm

What Is Interpolation Search Algorithm?

Interpolation Search Program In C

Jump Search Algorithm

Jump Search Algorithm

Jump Search Program In C

Binary Search Algorithm

What Is Binary Search Algorithm?

How Binary Search Algorithm Works

Binary Search Program In C

Linear Search Algorithm

What Is Linear Search Algorithm?

Linear Search Program In C