Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Before we start messing with the actual code, I'll explain a very little bit about how the find function works. It does a linear search,
Before we start messing with the actual code, I'll explain a very little bit about how the find function works. It does a linear search, using a variable called i for "index" to keep track of which element of the array called a just like in the pseudocode! is being compared with the search value called val during a specific execution of the while loop. i has an initial value of because array positions start at in JavaScript, as mentioned in the slides. The while loop will exit for one of two reasons:
the value of i is no longer less than the length of the array, in which case the linear search has not found value val in a or
value val has been matched to an element of array a in which case the value of i is the position of value val in a
So what does that mean? It means that if variable i ends up with a value less than the length of the list being searched a the search value, val was, indeed found in the list. Otherwise the value of i reached the length of the list being searched the value val is not one of the elements of the list a and the search failed. The rest of the program learns of this by way of the statement
return i;
in the find function. return causes the function to end and for any value that follows the word "return" to be given back to whichever statement called the find function. In this test program, that happens to be the statement
var pos finda val;
in the reportresult function. I chose the variable name pos because, as you may have suspected, it is short for "position", as in the position at which value val was found.
Okay, this all means that if we're going to use the same test code when we create our binary search version of find, we need to make sure it returns either the position or index of the search value in the listarray being considered, or the length of the list if the search value isn't in the list.
Back to the code:
Delete all the statements in the block of the find function but leave its opening and closing curly brackets in place.
function finda val
Everything else you must do for this lab will go on new lines between those curly brackets.
Now let's look back at that pseudocode. It starts off by creating a bunch of what look like variables, two of which conveniently have the same names we've been using, a to represent the array or list containing the various sorted values, and val representing the value we want the function to search for. Now, the Programming slides talk about information being conveyed to functions by way of arguments, which are the things that go inside the round brackets in a function call like
reportresult wordlist, "cat";
Inside the function itself, the values of the arguments become the values of the corresponding parameters, which is what the a and val are in
function finda val
So that means, we already have our a and our val from the pseudocode and don't need to recreate them with variable declarations. We DO need to do that, however, for the other variablelike things in the pseudocode, namely n low, high, and when we get to it mid.
Start with n It's needs to be initialized have its first value set to the length of a You can see from the original code that there are a couple of references to alength. Length is a property of arrays in JavaScript, and alength computes to the length of a That means your line declaring n the first line inside those curly brackets, should be
var n alength;
and yes, I know, we already had a statement that contained that, and I told you to erase it What can I say? Sometimes it pays to start over.
All right, so that's how you declare a variable. Now,
do the same for low and high, letting the pseudocode guide you as to what their initial values should be Remember the var keyword, and the semicolons ; statement terminators at the end of each line.
You should be ready to write your while loop. For guidance to the syntax, look at the while loop in the original code. It has a reasonably elaborate Boolean expression in its round brackets. Your replacement will be much simpler. Note that the "less than or equal to operator you'll need is this: a less than sign immediately followed by an equals sign. Remember the while loop's opening and closing curly brackets! All right,
create the first and last lines of your while loop with its opening and closing curly brackets which you'll fill in later Remember to put your Boolean expression in round brackets.
Notice from the pseudocode that all the statements in it are indented at least one level. Make sure yours match! It just makes the code tidier and easier to understand.
Inside your while loop:
Declare and initialize the mid variable. For this, you'll need to know how to do a floor operation in JavaScript. If you're not sure what floor functions do Google it It happens that JavaScript has a library of mathematics functions ca
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started