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. 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.
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.
The following 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  sequentialsearch(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  sortedsequentialsearch(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).

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.
Here's the code for binary search:
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 worst-case time for binary search is proportional to log2 N: the number of times N can be divided in half before there is nothing left. Using big-O notation, this is O(log N).

The binary search technique can also be implemented using non recursive iterative way
C program to implement iterative Binary Search
#include <stdio.h>
// A iterative binary search function. It returns
// location of k in given array  A[l..r] if present,
// otherwise -1
int binarysearch(int A[], int l, int r, int k)
{int m;
while (l <= r)
{
m = l + (r-1)/2;
// Check if k is present at mid
if (A[m] == k)
return m;

// If k greater, ignore left half
if (A[m] < k)
             l = m + 1;

// If k is smaller, ignore right half
else
             r = m - 1;
}
// if we reach here, then element was
// not present
            return -1;
}
int main(void)
{
int A[30];
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-1, 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
  6. 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.
    app autoketing
    https://apps.shopify.com/shipping-bar-master
    https://bit.ly/2BXG37u

    ReplyDelete
  7. Thank you very much for sharing this useful information, hope it will help many people and share it to more people know it.
    currency converter master, currency converter box by autoketing, autoketing

    ReplyDelete

Post a Comment

Popular posts from this blog

KTU C programming question paper and evaluation scheme

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY SECOND SEMESTER B.TECH DEGREE EXAMINATION, MAY 2017 CS 100 COMPUTER PROGRAMMING (CS, IT) SCHEME OF EVALUATION
PART A 1 An identifier is a sequence of characters invented by the programmer or to identify or name a specific object. The sequence of characters may be letters, digits, and special character ‘_’known as an underscore Rules: i)Identifiers should start with alphabets. ii)Identifiers are case sensitive iii)A numeric digit should not be the first character iv)Identifier name should not be a keyword v)Identifier may be of any reasonable length 1mark






2mark 2 Associativity defines the direction, left to right or right to left in which operator act upon its operands Unary operators have associativity is from right to left. For examplein the expression &--x, pre decrement works first and then address of operator works Direction + example<

Files in C

A file is a repository of data that is stored in a permanent storage media, mainly in secondary memory. In order to use the files we should learn how to read information from a file and how to write information into a file. A very important concept in C is the stream.The stream is a common logical interface to the various devices( files).A stream is linked to a file while using an open operation. A stream is disassociated from a file while using a close operation. The current location, also referred to as the current position, is the location in a file where the next fie access will occur.There are two types of streams text and binary. The following are some difference between text and binary files ·Text file is human readable because everything is stored in terms of text. In binary file everything is written in terms of 0 and 1, therefore binary file is not human readable. ·A newline(\n) character is converted into the carriage return-linefeed combination before being written to the d…