313
532
178
902
422
562Suppose the program had to look for the customer ID 413. With an unsorted array, a program would
have to match the ID 413 to each element in the array.
If the arrays contained hundreds or thousands of values instead of only six, the computer would take
longer to realize unmatched searches because each search would require that each element be looked
at. However, if the values were always sorted, a program would not always have to scan through the
entire list before realizing that a match would not be found. Here is the same list of values sorted
numerically, from low to high customer IDs:
178
313
422
532
562
902A sorted list makes the search faster. Now if you search for customer ID 413, your program can stop
searching after looking at only three array values. 422 is the third element, and because 422 is
greater than 413, your program can stop searching. It can stop searching because 422 comes after 413.
NoteIn extreme cases, searching a sorted array is not necessarily faster than sorting using an
unsorted array. For instance, if you were searching within the previous list for
customer ID 998, your program would have to search all six values before realizing
that 998 was not in the list.The following program is a combination of the customer ID searching program shown in the previous
chapter and the sorting routine shown in this chapter. The customer ID values are sorted, and then the
user is asked for a customer ID to find. The program then determines whether the customer’s balance
is less than $100. However, if the ID is not in the list, the program terminates the search early. Keep
in mind that having only 10 array values makes this program seem like overkill, but if there were tens
of thousands of customers, the code would not be different.
Click here to view code image
// Example program #2 from Chapter 23 of Absolute Beginner's Guide
// to C, 3rd Edition
// File Chapter23ex2.c
/* This program searches a sorted list of customer IDs in order to
get credit totals */