CHAPTER 12
SEARCHING: TO LOOK AND TO FIND
The computer was invented to perform complex mathematical computations, however this trend has changed and the computer has become more of a searching machine (engine). Non-stop, this machine looks to find proper matches, travel destinations, inventories, personal files, or even previous computations. In fact, searching is the center of most computer applications and increasingly dominates all aspects of our home, school, and office applications. Many algorithms have been developed to perform these searches, however, some searching algorithms are easy, some are difficult, and some are faster than others. Among the searching algorithms we can name sequential (linear) search, binary search and hashing. Each of these searches has their own advantages and disadvantages. One can argue that, with the high speed and memory size of todays computer, linear search would be sufficient for relatively small data sets. But, as the amount of data overwhelmingly increases, there is as need to explore alternative algorithms for searching. Hashing performs best in certain situations in comparison to other searching algorithms. Another efficient searching algorithm is known as search tree built on a data structure called tree. The data on a tree is stored in a fashion representing the branches of a tree and a root, interestingly it should be viewed upside down. The tree-searching algorithm can be difficult to understand and program. Understanding and analyzing various searching techniques using criteria such as consumption of computer time and/or space enables one to choose and decide on a proper search technique.
SEARCH PROGRAM STEPS
Every search program consists of the following three major steps.
1. Interaction
2. Look at existing information
3. Responding back
In the interaction step, the program asks the user to enter a proper request; and user responds by inputting the data, usually through the keyboard. In the second step, the program will take the requested information (search key) and search through existing information that is stored in a file, array, memory location, or any other data structures. The program then responds back to say whether or not the information was found.
SEARCH EXAMPLES
The following list is some of the search examples:
1. Computer user name and password
2. ATM and account validation
3. Grocery shopping
4. IRS or governments inquiries
5. School administration, Motor vehicle Dept.
6. Entire search engines, etc.
A SIMPLE SEARCH: PASSWORD VALIDATION
The following program demonstrates a simple search program for a password validation. The program asks the user to enter a password; if the entered password is equal to 876123 it will display a success. After three unsuccessful attempts, the program will display the message "SORRY NO MORE". In reality, password checking is much more complex than what is here but conceptually the idea is the same.
SEARCH TO GUESS YOUR MIND
Think of a number and interact with the following program, in a few attempts the program will guess your number. For example, if the guessed number is within range of 1 to 1024, the number will be found it with less than 20 guesses. Similarly for a million numbers it take less than forty guesses. It is possible to optimize the Guess Program by asking questions such as "IS IT LESS OR MORE? L/M ". In addition, the below guess program can be modified to include other subject matters such as guessing an animal, having an intelligent conversation or becoming a diagnostic system detecting an illness.
1. #include <iostream>
2. using namespace std;
3. main(){
4. int low=1, high=1024,mid,guess;
5. char reply;
6. cout<<"\tTHINK OF A NUMBER BETWEEN 1 AND 1024"<<endl;
7. cout<<"\t I WILL FIND IT IN LESS THAN 20 GUESSES"<<endl;
8. for (guess=19;guess>=0;guess--){
9. mid=(low+high)/2;
10. cout<<"IS IT: "<<mid<<" y/n?";
11. cin>>reply;
12. if (reply=='y'){
13. cout<<" I WON"<<endl;
14. return 1; }//IF
15. else {
16. cout<<guess<<" GUESSES LEFT: "<<endl;
17. guess--;
18. cout<<"IS IT LESS:y/n?";
19. cin>>reply;
20. cout<<guess<<" GUESSES LEFT: "<<endl;
21. if (reply=='y')high=mid+1;
22. else low=mid-1;}//ELSE
23. }//FOR
24. cout <<"\t IT IS HARD TO READ YOUR MIND "<<endl;
25. }//MAIN
Figure 12.2b Output of Guess Program
If we divide the range of numbers each time into halves, therefore the order of magnitude would be log2N. Therefore, for the range of 1024 =210, there would be a maximum of 10 guesses and for up to 1,047,576=220, only a maximum of 20 guesses is needed. However, for the program you can have the maximum integer of the system by using
const INT_MAX in the header file #include <limit.h>.
LINEAR SEARCH OR SEQUENTIAL SEARCH
Having a series of data, how do you look for (search) an item? You go through the list of items one by one until you find the item (search succeeded) or until the list is exhausted (search failed). This searching behavior, which sequentially visits each item, is known as sequential or linear search.
LINEAR SEARCH THROUGH A FILE
The following program illustrates the linear search through a file. Each time an item is accessed from the file it is compared with the item in question. If the search succeeds the program will prompt an appropriate message or take an action. In case of search failure program will prompt the failure. Accessing the data each time from the file can be cumbersome and it will slow the speed of the search. For the sake of simplicity the input file has only one set of items such as an employee's identification. The other information such as salary and department can be added without making the program much bigger. By adding the other information the input access in the following program will become as follows: fin>>empid>>>salary>>dept.
1. #include<iostream>
2. #include<fstream>
3. using namespace std;
4. main( ){
5. int searchid, empid;
6. cout<<"ENTER THE SEARCH ID: ";
7. cin>>searchid;
8. ifstream fin("employeeid.in");
9. while(fin>>empid){
10. if(empid==searchid){
11. cout<<"EMPLYEE FOUND "<<endl;
12. return 1; }//IF
13. }//WHILE
14. cout<<"NOT FOUND:"<<endl;
15. fin.close();
16. return 0;
17. }//MAIN
LINEAR SEARCH THROUGH AN ARRAY
Files are a good medium to store massive data. However, it is possible to read the data into an array before processing the search since working with arrays is faster and data can be revisited randomly. Alternatively, data can be entered into an array via keyboard or the array can be initialized inside the program itself. Array initialization inside the program can be beneficial if the size of data is small in order avoid unnecessary steps in accessing data when explaining the algorithm.
LINEAR SEARCH PROGRAM
The following program demonstrates a linear (sequential) search scanning through an array. Items are stored in an array called slot. The user interacts with the program by entering the search key. A linear search function is called to look for the search key in the array. As soon as the search key is matched with one item of slot, the function returns the index of matching slot. At the end, if there is no match and the loop is terminated, an invalid index 1 is returned.
1. #include<iostream>
2. using namespace std;
3. linearsearch(int slot[ ],int searchkey,int n){
4. for(int i=0; i<n;i++) if (searchkey==slot[i]) return i;
5. return -1; }//LINEARSEARCH
6. main(){
7. int slot[]={8,3,1,7,9};
8. const int N=5;
9. int searchkey,index;
10. cout<<"ENTER THE SEARCH KEY:";
11. cin>>searchkey;
12. index=linearsearch(slot,searchkey,N);
13. if (index==-1) cout <<"NOT FOUND"<<endl;
14. else cout<<" FOUND IN LOCATION: "<<index<<endl;
15. return 0; }// MAIN
Figure 12.4b Output of linear search program
SORTED LINEAR SEARCH
A linear search must search through the entire unsorted data to determine if a match exists. However, if the data are sorted, a linear search will only carry out the searching process as long as the search key is greater than the data.
How does the linear search find the search key 5 from the following sorted data 3, 6, 8, 10, 12?
The search will begin by determining if the search key 5 is greater than the first data 3. If so, the process will continue with the next element of the data until the condition becomes false. There are two possibilities for the condition to become false: one is when the last element of the data is examined and the second is when the search key is equal to the data.
SORTED LINER SEARCH PROGRAM
In the following program, the sorted data is stored in an array called slot. To search for an item, the searchkey is compared with each element of the array and the index is incremented as long as searchkey is greater than the current element of the array. The condition of the loop will turn to false when searchkey is no longer greater than slot[i]. The search is successful when the searchkey is equal to slot[i], otherwise the search fails.
1. #include<iostream>
2. using namespace std;
3. main(){
4. int slot[]={1,3,7,8,9};
5. const N=5;
6. int searchkey,i=0;
7. cout<<"ENTER THE SEARCH KEY:";
8. cin>>searchkey;
9. while(searchkey>=slot[i]) {
10. if (searchkey==slot[i]){cout<<" FOUND "<<slot[i]<<endl; return 1;}
11. i++;
12. }//WHILE
13. cout<<" NOT FOUND "<<endl;
14. return 0; }//MAIN
