Finding things is an unwanted pastime for humans. “Where are the good scissors?” “Who has seen the cat?” “What happened to all my money?” These issues don’t exist for a program that dutifully locates any data tidbit without complaint. Finding the smallest needle in the largest haystack isn’t an issue for a computer.

Consider the following code, which searches an array of integers. The code obtains the array’s size and asks the user to input a key value. The program loops through all elements in the array to scan for the input value. The results are reported.

2025_01_11-Lesson-a.c

#include <stdio.h>

int main()
{
    int v[] = { 23, 25, 1, 17, 20, 14, 3, 19 };
    int size,key,x;

    /* obtain array size */
    size = sizeof(v)/sizeof(int);

    /* locate a value */
    printf("Input key value: ");
    scanf("%d",&key);
    for( x=0; x<size; x++ )
    {
        if( v[x]==key )
        {
            printf("Key %d found!\n",key);
            return 0;
        }
    }
    printf("Key %d not found.\n",key);

    return 0;
}

Here’s sample output:

Input key value: 14
Key 14 found!

The code is rather simple, but is it efficient? Does it represent the best way to locate a value — or any information — in a collection of data? One way to tell is to increase the scale.

The following code update uses the makedata() function to generate up to 1,000 integer values in the range of 1 through 999.

2025_01_11-Lesson-b.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int *makedata(int s)
{
    int x,*data;

    /* allocate 'size' storage */
    data = malloc( sizeof(int) * s );
    if( data==NULL )
    {
        fprintf(stderr,"Unable to allocate memory\n");
        exit(1);
    }

    /* assign random values, 1 through 999 */
    for( x=0; x<s; x++ )
        *(data+x) = rand() % 999 + 1;

    return(data);
}

int main()
{
    int *v,size,key,x;

    /* obtain size 'n' 100 < n < 1000 */
    srand( (unsigned)time(NULL) );        /* seed randomizer */
    size = rand() % 900 + 100;
    printf("Dataset size = %d\n",size);

    /* create data */
    v = makedata(size);

    /* locate a value */
    printf("Input key value: ");
    scanf("%d",&key);
    for( x=0; x<size; x++ )
    {
        if( *(v+x)==key )
        {
            printf("Key %d found!\n",key);
            return 0;
        }
    }
    printf("Key %d not found.\n",key);

    /* clean-up */
    free(v);
    return 0;
}

As random values, the program can’t guarantee that a specific key can be located, but it does take longer to search through the dataset. Here’s a sample run:

Dataset size = 995
Input key value: 123
Key 123 found!

Call it dumb luck that I could pluck out a legitimate value from 995 random values. In fact, nothing in the code guarantees that a value is there or isn’t repeated several times. The point is that the larger and more complex the data, the more time is consumed searching. Imagine a dataset with millions of records and trying to locate a specific one? Sure, the program finds what you’re searching for . . . eventually.

Just as with sorting data, techniques are available to make finding data more efficient. One of them is the binary search. It uses a magical algorithm that quickly locates a key value in a sorted data set. In fact, just like sorting has qsort() function, the binary search has the bsearch() function in the C library. These two functions go hand-in-hand.

Starting with next week’s Lesson, I cover the bsearch() function and how it’s used to quickly and efficiently locate information.