C Programs

C Programming – Searching

Programs at a Glance

This section lists the programs covered under Searching Techniques in C. Click on a program title to jump directly to its detailed explanation.

  1. Linear Search Using Non-Recursive Function
  2. Binary Search Using Non-Recursive Function

Linear Search Using Non-Recursive Function

Problem Statement

Write a C program that uses a non-recursive function to search for a key value in a list of integers using linear search.

Student-Friendly Algorithm
  1. Start the program.
  2. Read the number of elements n.
  3. Read n integers into an array.
  4. Read the key element to be searched.
  5. Call the function linearSearch(a, n, key) to search for the key.
  6. If the function returns a valid position (not −1), display the position.
  7. Otherwise, display a message that the element is not found.
  8. Stop the program.
C Program

#include <stdio.h>

int linearSearch(int a[], int n, int key) {
    int i;
    for (i = 0; i < n; i++) {
        if (a[i] == key)
            return i + 1;   // Return position (1-based index)
    }
    return -1;              // Key not found
}

int main() {
    int a[50], n, key, pos, i;

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

    printf("Enter array elements:\n");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

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

    pos = linearSearch(a, n, key);

    if (pos != -1)
        printf("Element found at position %d\n", pos);
    else
        printf("Element not found\n");

    return 0;
}
Sample Output

Enter number of elements:
5
Enter array elements:
10 25 30 15 40
Enter key element to search:
15
Element found at position 4
Explanation

Linear search scans the array from the first element to the last, comparing each element with the key. As soon as a match is found, the function returns the position; if the end of the array is reached with no match, it returns −1.

This method is simple and works on both sorted and unsorted arrays, but it may be slow for large lists because every element might need to be checked in the worst case.

2. Binary Search Using Non-Recursive Function

Problem Statement

Write a C program that uses a non-recursive function to search for a key value in a sorted list of integers using binary search.

Student-Friendly Algorithm
  1. Start the program.
  2. Read the number of elements n.
  3. Read n integers into an array in sorted order.
  4. Read the key element to be searched.
  5. Call the function binarySearch(a, n, key).
  6. Inside the function, set low = 0 and high = n − 1.
  7. Repeat while low <= high:
    • Compute mid = (low + high) / 2.
    • If a[mid] equals the key, return mid + 1 (position).
    • If the key is smaller than a[mid], move the search range to the left half by setting high = mid − 1.
    • Otherwise, move the search range to the right half by setting low = mid + 1.
  8. If the loop finishes without finding the key, return −1.
  9. In main(), display the position if found, otherwise display “not found”.
  10. Stop the program.
C Program

#include <stdio.h>

int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (a[mid] == key)
            return mid + 1;          // Return position (1-based index)
        else if (key < a[mid])
            high = mid - 1;          // Search in left half
        else
            low = mid + 1;           // Search in right half
    }

    return -1;                       // Key not found
}

int main() {
    int a[50], n, key, pos, i;

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

    printf("Enter sorted array elements:\n");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

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

    pos = binarySearch(a, n, key);

    if (pos != -1)
        printf("Element found at position %d\n", pos);
    else
        printf("Element not found\n");

    return 0;
}
Sample Output

Enter number of elements:
6
Enter sorted array elements:
5 10 15 20 25 30
Enter key element to search:
20
Element found at position 4
Explanation

Binary search requires the array to be sorted and works by repeatedly halving the search range. At each step, the middle element is compared with the key, and only the left or right half is kept for further searching, which greatly reduces the number of comparisons.

Because the search interval is divided by two on each iteration, binary search has much better performance than linear search on large sorted arrays, with time complexity proportional to log2(n).