Searching in C Programming

by

Searching is the process of finding element in a given list. In this process we check item is available in given list or not.

Type of searching

  1. Internal search
  2. External search

Internal Search: In this search, Searching is performed on main or primary memory.
External Search: In this search, Searching is performed in secondary memory.

There are basically three types of searching techniques:
 Linear or sequential search
 Binary search
 Interpolation search

Linear/ Sequential Search
Linear/Sequential searching is a searching technique to find an item from a list until the particular item not found or list not reached at end. We start the searching from 0th index to N-1 index in a sequential manner, if particular item found, returns the position of that item otherwise return failure status or -1.

10141926273133354244
Linear Search

Algorithm
Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

#include <stdio.h>
/*Function to search item from list*/
int LinearSearch(int ele[], int n, int item)
{
int pos = -1,k;
for( k = 0; k < n; k++ )
{
if( ele[k] == item )
{
pos = k;
break;
}
}
return pos;
}
void main()
{
int ele[10],k,n,item,pos;
printf("Enter no of elements : ");
scanf("%d",&n);
printf("\nEnter Items : \n");
for( k = 0; k < n; k++)
scanf("%d",&ele[k]);
printf("\n\nEnter Item To Be Searched : ");
scanf("%d",&item);
pos = LinearSearch(ele, n, item);
if( pos >= 0 )
printf("\nItem Found At Position : %d\n",pos+1);
else
printf("\nItem Not Found In The List\n");
getch();
}

Binary Search
For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of binary search with a pictorial example. The following is our sorted array and let us assume that we need to search the location of value 31 using binary search.

10141926273133354244

First, we shall determine half of the array by using this formula −
mid = low + (high – low) / 2
Here it is, 0 + (9 – 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

10141926273133354244

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the value at location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.

3133354244

We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high – low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

10141926273133354244

The value stored at location 7 is not a match, rather it is more than what we are looking for.
So, the value must be in the lower part from this location.

3133

Hence, we calculate the mid again. This time it is 5.

3133

We compare the value stored at location 5 with our target value. We find that it is a match.

31

We conclude that the target value 31 is stored at location 5.
Binary search halves the searchable items and thus reduces the count of comparisons to be made to very less numbers.
Algorithm
BINARY SEARCH (LIST, N, ITEM, LOC, LOW, MID, HIGH)

  1. Set LOW := 1; LOW := N;
  2. Repeat step a to d while LOW <= HIGH and ITEM != LIST(MID)
    a. Set MID := (LOW + HIGH)/2
    b. If ITEM = LIST(MID), then
    i. Set LOC := MID
    ii. Return
    c. If ITEM < LIST(MID) then
    i. Set HIGH := MID – 1;
    d. Otherwise
    i. Set LOW := MID + 1;
  3. SET LOC := NULL
  4. return
#include <stdio.h>
/*Function to search item from sorted list*/
int BinarySearch(int ele[], int n, int item)
{
int pos = -1,k,low,mid,high;
low = 0;
high = n-1;
while( low <= high )
{
mid = (low + high)/2;
if( ele[mid] == item )
{
pos = mid ;
break;
}
else if( item > ele[mid] )
low = mid + 1;
else
high = mid - 1;
}
return pos;
}
void main()
{
int ele[10],k,n,item,pos;
printf("Enter no of elements : ");
scanf("%d",&n);
printf("\nEnter Items : \n");
for( k = 0; k < n; k++)
scanf("%d",&ele[k]);
printf("\n\nEnter Item To Be Searched : ");
scanf("%d",&item);
pos = BinarySearch(ele, n, item);
if( pos >= 0 )
printf("\nItem Found At Position : %d\n",pos+1);
else
printf("\nItem Not Found In The List\n");
getch();
}

Difference between Linear Search and Binary Search

Linear SearchBinary Search
Sorted list is not required.Sorted list is required.
It can be used in linked list implementation.It cannot be used in liked list implementation.
It is suitable for a list changing very frequently.It is only suitable for static lists, because any change requires resorting of the list.
The average number of comparison is very
high.		The average number of comparison is relatively
slow.

Interpolation Search
An Interpolation Search is a type of searching algorithm. An Interpolation Search is an improvement over Binary Search for scenarios where the values in a sorted array are uniformly distributed. Binary Search goes to the middle element to check. On the other hand, Interpolation Search may go to different locations according to the value of the key being searched. For example, if the value of the key is close to the last element, Interpolation Search is likely to start search toward the end side.

This technique is used if the items to be searched are uniformly distributed between the first and the last location. This technique is a simple modification in the binary search when MID is calculated.
Mid = low + (high – low) * ((item – LIST[low]) / (LIST[high] – LIST[low]));

Advantages

  1. If the items are uniformly distributed, the average case time complexity is log2(log2(n)).
  2. It is considered improvement in binary search.
    Disadvantages
  3. The calculation of mid is complicated. It increases the execution time.
  4. If the items are not uniformly distributed, interpolation search will have very poor behavior.
    Algorithm
    As it is an improvisation of the existing BST algorithm, we are mentioning the steps to search the ‘target’ data value index, using position probing −
    Step 1 − Start searching data from middle of the list.
    Step 2 − If it is a match, return the index of the item, and exit.
    Step 3 − If it is not a match, probe position.
    Step 4 − Divide the list using probing formula and find the new
    midle.
    Step 5 − If data is greater than middle, search in higher sub-list.
    Step 6 − If data is smaller than middle, search in lower sub-list.
    Step 7 − Repeat until match.

Pseudocode

A → Array list
N → Size of A
X → Target Value
Procedure Interpolation_Search()
Set Lo → 0
Set Mid → -1
Set Hi → N-1
While X does not match
if Lo equals to Hi OR A[Lo] equals to A[Hi]
EXIT: Failure, Target not found
end if
Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
if A[Mid] = X
EXIT: Success, Target found at Mid
else
if A[Mid] < X
Set Lo to Mid+1
else if A[Mid] > X
Set Hi to Mid-1
end if
end if
End While
End Procedure

Leave a Comment