Skip to main content

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;
}


Comments

  1. I have read all your articles. I wonder why you can write them. They are easy to understand and accessible. They help me much too. I'm thankful if you can upload more posts later. Thanks for your sharing.
    Hướng dẫn đăng ký B30 VinaPhone, Đăng ký Mimax sinh viên VinaPhone, Đăng ký Mimax50 VinaPhone, Đăng ký 3G VinaPhone 1 ngày chỉ 5K,7K,10K

    ReplyDelete
  2. I'm trying to learn more knowledge and your articles are so useful for me. I can understand them easily. They aren't science rocket. I even can apply them in ordinary life. I'm grateful for your sharing. I hope you will write often and post more articles. email-with-love free online2018,apps email-with-love, http://dichvuvina.vn

    ReplyDelete
  3. Hold writing.Thank you for your article post.Really getting excited about read more. Really Cool.I enjoy and recognize your post.Thanks Again.
    sale pop online
    sales pop master app

    ReplyDelete
  4. Hold writing.Thank you for your article post.Really getting excited about read more. Really Cool.I enjoy and recognize your post.Thanks Again.
    Discount master app


    Discount master app

    ReplyDelete
  5. For space outside the milk tea shop closer to nature, outdoor space should use speakers with greater capacity, products such as garden speakers, imitation stone speakers, are products with designs The most natural to create interesting feeling when enjoying. Because it must work in the weather conditions heat so the shell is made very firmly with high durability, the quality of the speaker is imported genuine. Good sound, making good clear sound even when used in wide space
    Gái gọi Mỹ Đình - Đình Thôn, gái gọi Nguyễn Khánh Toàn, gái gọi hà nội, gái gọi Phố Cổ - Quán Sứ

    ReplyDelete

Post a Comment

Popular posts from this blog

KTU Mandatory C programs for Laboratory and Solutions

LIST OF LAB EXPERIMENTS 1. Familiarization of Hardware Components of a Computer 2. Familiarization of Linux environment – Programming in C with Linux 3. Familiarization of console I/O and operators in C     i) Display “Hello World”     ii) Read two numbers, add them and display their sum     iii) Read the radius of a circle, calculate its area and display it 4. Evaluate the arithmetic expression ((a -b / c * d + e) * (f +g))   and display its solution. Read the values of the variables from the user through console 5. Read 3 integer values, find the largest among them. 6. Read a Natural Number and check whether the number is prime or not 7. Read a Natural Number and check whether the number is Armstrong or not 8. Read n integers, store them in an array and find their sum and average 9. Read n integers, store them in an array and search for an element in the    array using an algorithm for Linear Search 10.Read n integers, store them in an array and sort the elements in t

PROGRAMMING IN C KTU EST 102 THEORY AND LAB NOTES

PROGRAMMING IN C  KTU  EST 102  THEORY AND LAB   COMMON FOR ALL BRANCHES About Me Syllabus Theory Syllabus Lab Model Question Paper University Question Papers and evaluation scheme Introduction( Lab) Introduction to C programming Linux History and GNU How to create a bootable ubuntu USB stick Installing  Linux Install Linux within  Windows Virtual Box and WSL Linux Basic Features and Architecture Basic Linux Commands Beginning C Programming Compiling C programs using gcc in Linux Debugging C program using gdb Module 1: Basics of computer hardware and software          Module-1 Reading Material Basics of Computer Architecture Hardware and Software System Software and Application Software  Programming Languages ( High level, Low level and Machine Language) and Translators ( Compiler, Interpreter, Assembler) Algorithm, Flowcharts and Pseudo code Program Development Structured Programming Basics of hardware ( video) Know about Motherboard(video) Know Universal Serial Bus ( USB) - video Lea

Input Output-printf() and scanf()

printf() and scanf() function in C   printf() and scanf() functions are inbuilt library functions in C programming language which are available in C library by default.These functions are declared and related macros are defined in “stdio.h” which is a header file in C language. We have to include “ stdio.h ” file as shown in below to make use of these printf() and scanf() library functions in C program. #include <stdio.h>   printf() function in C   In C programming language, printf() function is used to print the “character, string, float, integer, octal and hexadecimal values” onto the output screen. Here’s a quick summary of the available printf format specifiers:   %c           character %d           decimal (integer) number (base 10) %ld         Long integer %e           exponential floating-point number %f           floating-point number %lf          double number %i            integer (base 10) %o         octal number (base 8) %s         a string of characters %u