Linear and Binary Search in C

Searching is one of the most common problems that arise in computing. Searching is the algorithmic process of finding a particular item in a collection of items. A search typically answers either True or False as to whether the item is present or not. On occasion it may be modified to return where the item is found. Search operations are usually carried out on a key field.

Consider searching for a given value k in an array A of size n. There are 2 basic approaches: sequential search and binary search.

Linear (Sequential) Search

When data items are stored in a collection such as a list or array , we say that they have a linear or sequential relationship. Each data item is stored in a position relative to the others. In C array, these relative positions are the index values of the individual items. Since these index values are ordered, it is possible for us to visit them in sequence. This process gives rise to our first searching technique, the sequential search or linear search.

Starting at the first item in the list, we simply move from item to item, following the underlying sequential ordering until we either find what we are looking for or run out of items. If we run out of items, we have discovered that the item we were searching for was not present.

Algorithm
Linear Search ( Array A, Value x)

Step 1: Set i to 0 

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

The following C function will return the position of an element k in an array A of size n.If the element is not present the function will return -1.
int linearsearch(int A[],int n ,int k)
{ int i;
for (i = 0; i < n; i++)
{
if (A[i]==k) return i;
}
return -1;
}

If the values are in sorted order, then the algorithm can sometimes quit and return false(-1) without having to look at all of the values in the array. If k is not in the array and if the current value is greater than k then we can return -1. Here's the code for this version:

int linearsearch(int A[], int n,int k)
{ int i;
// precondition: A is sorted (in ascending order)
for (i = 0;i < n; i++)
{
if (A[i]==k) return i;
if (A[i]>k) return -1;
}
return -1;
}
The worst-case time for a sequential search is always O(N).

include<stdio.h>

main()
{
int arr[50],k,i,n,flag=0;
printf(“Enter the number of elements n\n”);
scanf(“%d”,&n);
printf(“Enter %d elements\n”,n);
for(i=0;i<n;i++)
{
scanf(“%d”,&arr[i]);
}
printf(“Enter a number to be search\n”);
scanf(“%d”,&k);
for(i=0;i<n;i++)
{
if(arr[i]==k)
    {
    flag=1;
    break;
    }
}
if(flag==1)
    printf(“%d is found in the list, at position %d\n”,k,i+1);
else
    printf(“%d is not in the list\n”,k);

}

Example

Initial array: [23, 34, 41, 65, 70]
Element to be searched: 65

Here are the steps:

Start at the beginning of the array.
Compare each element with the element we are searching for (65 in this case).
If the element is found, return its index. If not found, return -1.

Here's the step-by-step process:

Compare 23 with 65. Not a match.
Compare 34 with 65. Not a match.
Compare 41 with 65. Not a match.
Compare 65 with 65. Match found at index 3.

So, the element 65 is found at index 3 in the array [23, 34, 41, 65, 70] when using linear search.

 

Binary Search

When the values are in sorted order, a better approach than the one given above is to use binary search. .The algorithm for binary search starts by looking at the middle item x. If x is equal to k, it quits and returns true(position). Otherwise, it uses the relative ordering of x and k to eliminate half of the array (if k is less than x, then it can't be stored to the right of x in the array; similarly, if it is greater than x, it can't be stored to the left of x). Once half of the array has been eliminated, the algorithm starts again by looking at the middle item in the remaining half. It quits when it finds k or when the entire array has been eliminated.

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log n). The list is partitioned into 2 after comparing the key element with middle element and hence the name binary search.

Algorithm
1.We start by comparing the element to be searched with the element in the middle of the list/array.
2.If we get a match, we return the index of the middle element and stop goto step 7.
3.If we do not get a match, we check whether the element to be searched is less or greater than in value than the middle element.
4.If the element/number to be searched is greater in value than the middle element, then we pick the elements on the right side of the middle element(as the list/array is sorted, hence on the right, we will have all the numbers greater than the middle number), and start again from the step 1.
5.If the element/number to be searched is lesser in value than the middle number, then we pick the elements on the left side of the middle element, and start again from the step 1.
6.When the entire array is eliminated and the element is not found display element not found.

7.stop.
Binary Search is useful when there are large number of elements in an array and they are sorted.
So a necessary condition for Binary search to work is that the list/array should be sorted.

Binary search Implementation without using function

#include <stdio.h>

int main(void)

{

int A[100],n,i,f,l,m,k;

int flag=0;

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

scanf("%d",&n);

printf("Enter the array elements in sorted order\n");

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

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

printf("Enter the key element to serach…\n");

scanf("%d",&k);

f=0;l=n-1;

while (f<= l)

{

m = (f+ l)/2;

// Check if k is present at mid

if (A[m] == k)

    {flag=1;break;}

// If k greater, ignore left half

if (A[m] < k)

  f = m + 1;

// If k is smaller, ignore right half

 else

    l= m - 1;

 }

if (flag==1)

   printf("key element %d is found at array loc=%d",k,m+1);

else

  printf("Element not found\n");

}

Binary search implementation using function( recursive function)

int binarysearch(int A[],int low,int high,int k)

{

// precondition: A is sorted (in ascending order)

if (low > high) return -1;

int middle = (low + high) / 2;

if (A[middle]==key) return middle;

if (k<A[middle]) 

{

// recursively search the left part of the array

return(binarysearch(A, low, middle-1, k));

}

else {

// recursively search the right part of the array

return binarysearch(A, middle+1, high, k);

}

}

The binary search technique can also be implemented using non recursive iterative way

C program to implement iterative(non recursive) Binary Search

#include <stdio.h>

// A iterative binary search function. It returns

// location of k in given array A[0..l] if present,

// otherwise -1

int binarysearch(int A[], int f, int l, int k)

{

int m;

while (f<= l)

{

m = (f+ l)/2;

// Check if k is present at mid

if (A[m] == k)

return m;

// If k greater, ignore left half

if (A[m] < k)

     f = m + 1;

// If k is smaller, ignore right half

else

    l= m - 1;

}

// if we reach here, then element was

// not present

return -1;

}

int main(void)

{

int A[100];

int k,n,i,result

printf(“Enter the number of elements\n”);

scanf(“%d”,&n);

printf(“Enter the of elements in sorted order\n”);

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

  scanf(“%d”,&A[i]);

printf(“Enter the key element to serach…\n”);

scanf(“%d”,&k);

result = binarysearch(A, 0, n, k);

(result == -1)? printf("Element is not present in array"): printf("Element is present at index %d", result);

return 0;

}