Linear and Binary Search

Searching in C

Searching is one of the most common problems in computing.
It is the algorithmic process of finding a particular item in a collection of items.

  • A search typically returns True/False depending on whether the item exists.

  • Sometimes it may also return the location/index of the item.

  • Search operations are usually carried out on a key field.

Consider searching for a value k in an array A of size n.

There are two basic approaches:

  1. Sequential (Linear) Search

  2. Binary Search

Linear (Sequential) Search

When data items are stored in a list or array, they have a linear/sequential relationship.

  • Each item is stored at a position relative to others.

  • In C arrays, these positions are index values.

  • Since indexes are ordered, we can visit elements one by one in sequence.

Working

  • Start from the first item.

  • Compare each element with the target.

  • Stop when:

    • The element is found, OR

    • All elements are checked.

Algorithm: Linear Search

Linear Search (Array A, Value x)

  1. Set i = 0

  2. If i >= n, go to step 7

  3. If A[i] == x, go to step 6

  4. Set i = i + 1

  5. Go to step 2

  6. Print Element found at index i → go to step 8

  7. Print Element not found

  8. Exit

C Function (Linear Search)

int linearsearch(int A[], int n, int k)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (A[i] == k)
            return i;
    }
    return -1;
}

Linear Search for Sorted Array (Optimized)

int linearsearch(int A[], int n, int k)
{
    int i;
    // precondition: A is sorted ascending
    for (i = 0; i < n; i++)
    {
        if (A[i] == k) return i;
        if (A[i] > k) return -1;
    }
    return -1;
}

Worst-case time complexity: O(N)

Complete Linear Search Program

#include <stdio.h>

int 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 searched\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);

    return 0;
}

Example

Array: [23, 34, 41, 65, 70]
Search element: 65

Steps:

  • Compare 23 → not match

  • Compare 34 → not match

  • Compare 41 → not match

  • Compare 65 → match at index 3

Binary Search

Binary search works only on sorted arrays.

Idea

  • Check the middle element.

  • If equal → return index.

  • If key < middle → search left half.

  • If key > middle → search right half.

  • Repeat until found or array exhausted.

Time Complexity: O(log n)

Algorithm: Binary Search

  1. Compare key with middle element.

  2. If match → return index → stop.

  3. If key > middle → search right half.

  4. If key < middle → search left half.

  5. Repeat until found.

  6. If array eliminated → print not found.

  7. Stop.

Binary Search Program (Without Function)

#include <stdio.h>

int main()
{
    int A[100], n, i, f, l, m, k, flag = 0;

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

    printf("Enter elements in sorted order\n");
    for(i = 0; i < n; i++)
        scanf("%d", &A[i]);

    printf("Enter the key element to search\n");
    scanf("%d", &k);

    f = 0;
    l = n - 1;

    while(f <= l)
    {
        m = (f + l) / 2;

        if(A[m] == k)
        {
            flag = 1;
            break;
        }

        if(A[m] < k)
            f = m + 1;
        else
            l = m - 1;
    }

    if(flag == 1)
        printf("Key element %d found at position %d", k, m+1);
    else
        printf("Element not found\n");

    return 0;
}

Binary Search Using Recursive Function

int binarysearch(int A[], int low, int high, int k)
{
    if(low > high) return -1;

    int middle = (low + high) / 2;

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

    if(k < A[middle])
        return binarysearch(A, low, middle-1, k);
    else
        return binarysearch(A, middle+1, high, k);
}

Iterative Binary Search Function

int binarysearch(int A[], int f, int l, int k)
{
    int m;

    while(f <= l)
    {
        m = (f + l) / 2;

        if(A[m] == k) return m;

        if(A[m] < k)
            f = m + 1;
        else
            l = m - 1;
    }
    return -1;
}

Binary Search Main Program

#include <stdio.h>

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

int main()
{
    int A[100], k, n, i, result;

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

    printf("Enter elements in sorted order\n");
    for(i = 0; i < n; i++)
        scanf("%d", &A[i]);

    printf("Enter the key element to search\n");
    scanf("%d", &k);

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

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

    return 0;
}

Write a C program for an institution that stores a list of allotted seat numbers for an exam hall using an array. The program should allow the user to: ( university question)
1. Input the total number of allotted seats, followed by the seat
numbers.
2. Prompt the student to enter a seat number they want to check.
3. Use a linear search algorithm to determine whether the entered
seat number exists in the list of allotted seats.
4. Display an appropriate allotment message.

#include <stdio.h>

int main() {
    int n, i, seatToCheck;
    int seats[100];
    int found = 0;

    /* 1. Input total seats and seat numbers */
    printf("Enter total number of allotted seats: ");
    scanf("%d", &n);

    printf("Enter the allotted seat numbers:\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &seats[i]);
    }

    /* 2. Seat number to check */
    printf("Enter seat number to check: ");
    scanf("%d", &seatToCheck);

    /* 3. Linear search */
    for (i = 0; i < n; i++) {
        if (seats[i] == seatToCheck) {
            found = 1;
            break;
        }
    }

    /* 4. Display result */
    if (found) {
        printf("Seat number %d is ALLOTTED. Please proceed to the exam hall.\n",
               seatToCheck);
    } else {
        printf("Seat number %d is NOT allotted. Please contact the exam office.\n",
               seatToCheck);
    }

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Programming in C GXEST204 - KTU 2024 scheme syllabus notes pdf ------- Dr Binu V P

About me About the course- Scheme and Evaluation GXEST204 Syllabus GXEST204 Model Question Paper GXEST204 Programming in C - KTU 2024 Scheme University Question Paper and Answer  Scheme GXEST204 Programming in C-May 2025  - KTU 2024 Scheme University Question Paper  and  Answer  Scheme  GXEST204 Programming in C-Dec 2025  - KTU 2024 Scheme Introduction to C Programming Beginning with C Programming Programming in C using gcc in Linux Debugging C Program using gdb Module-1 C Fundamentals Structure of a C Program Variables and constants in C Escape Sequences Keywords and Identifiers Data Types and qualifiers   Data Type summary Primitive and Derived Data Type Preprocessor Directive Header Files in C Input-output printf() and scanf() Operators, precedence and expressions Bitwise operators in C Simple Programs to Begin with Control Statements Control statements in C if-else statement , sample programs, programs to try switch case statement, ...
Read more

Structure of a C Program

Image
Basic Structure of a C Program A C program is divided into different sections. There are six main sections in a basic C program. The Six Sections Are: Documentation Section Include / Link / Preprocessor Section Definition Section Global Declarations Section (functions and variables) Main Function Subprogram Functions Overview Now let us learn about each of these sections in detail. Figure: Basic Structure Of C Program Sample Program The C program below finds the area of a circle using a user-defined function and a global variable PI holding the value of π. /* File Name: areaofcircle.c Author: Abhijith Date: 06/05/2021 Description: A program to calculate area of circle. User enters the radius. */ # include <stdio.h> // Link section # define PI 3.14 // Definition section float area ( float r); // Global declaration /****************************/ int main () // Main function { float r;...
Read more

Single and Multi Dimensional Arrays

Image
Arrays in C An array is a collection of data items, all of the same type , accessed using a common name . A one-dimensional array is like a list (vector) . A two-dimensional array is like a table (matrix) . Arrays can also have more dimensions . Memory Characteristics Array elements are stored in contiguous (adjacent) memory locations . Elements can be randomly accessed . The address of each element can be calculated using: Base address Size of each data element Declaring Single Dimensional Arrays Array variables are declared like normal variables, except: The variable name is followed by square brackets [ ] The brackets contain the array dimension (size) Rules Dimensions must be positive integers or constant expressions . In C99 , variables may be used as sizes if they hold a positive value at declaration. Memory is allocated only once when declared. Array size does not change later , even if the variable used changes. E...
Read more