As usual, create a directory to hold today's activities:
$ mkdir ~/cs170/labs/lab14 $ cd ~/cs170/labs/lab14
By now, you know enough about programming to consider yourself a "coder." Given a task, you can probably find some way to get a program to complete it. However, being able to code is only part of the way to becoming a real programmer. Being able to program involves being able to plan programs well, and being able to use the most efficient mechanisms possible.
Today, we will talk about two different algorithms for searching. Which algorithm should we use in which scenarios? How do these algorithms compare? Let's explore these, and more.
The most straight forward method of determining if and where some item is in a list is a process known as Linear Search. With linear search, we examine every element in the list starting from the front of the list. If we find the element we are looking for, we return the index. If we look through the entirety of the list and don't find the item, we return some value representing the fact that the element was not in the list.
In a file called search.cc, write a function
called linearSearch(int anArray[], int size, int
toFind). This function takes three parameters: an array
of integers, the size of the array of integers, and an integer to
look for. This function should return
True if an_integer is in the array, and False otherwise. You should use
#include <iostream>
using namespace std;
#define ARRAY_SIZE 6
// ... SNIP ...
int main() {
int myArray[ARRAY_SIZE] = {4, 8, 15, 16, 23, 42};
if(linearSearch(myArray, ARRAY_SIZE, 23)){
cout << "23 is in the array!" << endl;
} else {
cout << "23 is not in the array!" << endl;
}
//This should output "23 is in the array!"
if(linearSearch(myArray, ARRAY_SIZE, 1)){
cout << "1 is in the array!" << endl;
} else {
cout << "1 is not in the array!" << endl;
}
//This should output "1 is not in the array!"
}
You should use a for loop to iterate through elements of the list. You should keep track of whether you have found the element you are looking for by using a boolean "accumulator"
You need to set up a default case, where you have searched through the entirety of the list and have not found the element in question. In this case, you should return False.
Linear search might take a very long time. However, our computers today are fast enough that even with very large lists we will not notice the difference between this and the other search mechanism discussed today.
Add to your program a function that will create a random list of integers of some specified size. Modify your program so that you use increasingly larger lists. Add a comment in your program which lists the point at which linear search starts taking a noticeable amount of time.
Note that for a fair comparison, you are going to need to always spend the most amount of time searching. What is this worst case going to be, given an arbitrary list?
Binary search is a searching technique that leverages additional knowledge about the contents of the list. Namely, it knows that the items in the list are in some order. If we have items in some order, we can leverage this knowledge of the relationships between elements, in an attempt to speed up our search process.
In your search.cc file, write a function
called binarySearch(int anArray[], int size, int
toFind). This function takes three parameters: an array
of integers, the size of the array of integers, and an integer to
look for. This function should return
True if an_integer is in the array, and False otherwise. You should use
the binary search algorithm for this function.
The steps for binary search are as follows. First, look at the element at the middle of the list. If that item is the string being searched for, you are done. If it is not, then you figure out which half of the list the toFind should appear. If the parameter toFind is less than the middle element, then toFind is in the left half of the list. Otherwise it is on the right. You then continue this process on the appropriate half of the list, until you find toFind. Of course, you also need to stop if you run out of elements to examine.
Make sure you test your code on all of the boundary conditions! It is easy to get the basic gist of this algorithm coded quite quickly, but you need to be able to handle the edge cases well.
To save yourself some time, you can use the built in sort function,
to sort an array for your testing purposes!
#include <iostream>
using namespace std;
#define ARRAY_SIZE 6
// ... SNIP ...
int main() {
int myArray[ARRAY_SIZE] = {4, 8, 15, 16, 23, 42};
if(binarySearch(myArray, ARRAY_SIZE, 23)){
cout << "23 is in the array!" << endl;
} else {
cout << "23 is not in the array!" << endl;
}
//This should output "23 is in the array!"
if(binarySearch(myArray, ARRAY_SIZE, 1)){
cout << "1 is in the array!" << endl;
} else {
cout << "1 is not in the array!" << endl;
}
//This should output "1 is not in the array!"
}
You should define two local variables in your
function: start and end. These
variables are going to represent the beginning and the end
of the list you are considering at this
point. start is going to be inclusive,
while end is exclusive.
The
arithmetic mean of start and end is the index of the element
you are examining at this iteration of the loop. You should
store this in a variable called mid.
To change where in the list you are examining, you simply need to modify start and end. Make sure you don't inadvertently create an infinite loop!
You will need to use a while loop for this, as opposed to a
for loop. You will want to stop your loop
when start is greater than (or equal
to) end. You also want to stop if you have
found the element you are looking for.
The true power of binary search is not that it is able to determine if an element is in the list, but how quickly it can do so. The number of comparisons necessary to determine whether or not an item is in a list should be less than that of linear search. Modify your functions so they output the number of comparisons needed to find an element.
Try your new functions with lists of various sizes. Can you define the pattern that emerges, as a function of the size of the list? Does the element being searched for affect your results? Can you find instances where linear is faster than binary?