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.
\n
\nConsider 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.<\/p>\n
\r\n#include <stdio.h>\r\n\r\nint main()\r\n{\r\n int v[] = { 23, 25, 1, 17, 20, 14, 3, 19 };\r\n int size,key,x;\r\n\r\n \/* obtain array size *\/<\/span>\r\n size = sizeof(v)\/sizeof(int);\r\n\r\n \/* locate a value *\/<\/span>\r\n printf(\"Input key value: \");\r\n scanf(\"%d\",&key);\r\n for( x=0; x<size; x++ )\r\n {\r\n if( v[x]==key )\r\n {\r\n printf(\"Key %d found!\\n\",key);\r\n return 0;\r\n }\r\n }\r\n printf(\"Key %d not found.\\n\",key);\r\n\r\n return 0;\r\n}<\/pre>\nHere’s sample output:<\/p>\n
Input key value: 14
\nKey 14 found!<\/code><\/p>\nThe 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.<\/p>\n
The following code update uses the makedata()<\/em> function to generate up to 1,000 integer values in the range of 1 through 999.<\/p>\n2025_01_11-Lesson-b.c<\/a><\/h3>\n\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <time.h>\r\n\r\nint *makedata(int s)\r\n{\r\n int x,*data;\r\n\r\n \/* allocate 'size' storage *\/<\/span>\r\n data = malloc( sizeof(int) * s );\r\n if( data==NULL )\r\n {\r\n fprintf(stderr,\"Unable to allocate memory\\n\");\r\n exit(1);\r\n }\r\n\r\n \/* assign random values, 1 through 999 *\/<\/span>\r\n for( x=0; x<s; x++ )\r\n *(data+x) = rand() % 999 + 1;\r\n\r\n return(data);\r\n}\r\n\r\nint main()\r\n{\r\n int *v,size,key,x;\r\n\r\n \/* obtain size 'n' 100 < n < 1000 *\/<\/span>\r\n srand( (unsigned)time(NULL) ); \/* seed randomizer *\/<\/span>\r\n size = rand() % 900 + 100;\r\n printf(\"Dataset size = %d\\n\",size);\r\n\r\n \/* create data *\/<\/span>\r\n v = makedata(size);\r\n\r\n \/* locate a value *\/<\/span>\r\n printf(\"Input key value: \");\r\n scanf(\"%d\",&key);\r\n for( x=0; x<size; x++ )\r\n {\r\n if( *(v+x)==key )\r\n {\r\n printf(\"Key %d found!\\n\",key);\r\n return 0;\r\n }\r\n }\r\n printf(\"Key %d not found.\\n\",key);\r\n\r\n \/* clean-up *\/<\/span>\r\n free(v);\r\n return 0;\r\n}\r\n<\/pre>\nAs 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:<\/p>\n
Dataset size = 995
\nInput key value: 123
\nKey 123 found!<\/code><\/p>\nCall 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.<\/p>\n
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()<\/em> function, the binary search has the bsearch()<\/em> function in the C library. These two functions go hand-in-hand.<\/p>\nStarting with next week’s Lesson<\/a>, I cover the bsearch()<\/em> function and how it’s used to quickly and efficiently locate information.<\/p>\n","protected":false},"excerpt":{"rendered":"Along with sorting, searching is another repetitive task that computer programs enjoy. Continue reading