Answered step by step
Verified Expert Solution
Link Copied!

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 0, because array positions start at 0 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 = find(a, val);
in the report_result 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 list/array 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 find(a, 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 1 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
report_result (word_list, "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 find(a, 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 variable-like 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 a.length. Length is a property of arrays in JavaScript, and a.length computes to the length of a. That means your line declaring n, the first line inside those curly brackets, should be
var n = a.length;
(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

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Security

Authors: Alfred Basta, Melissa Zgola

1st Edition

1435453905, 978-1435453906

More Books

Students also viewed these Databases questions

Question

Discuss the various types of policies ?

Answered: 1 week ago

Question

Briefly explain the various types of leadership ?

Answered: 1 week ago

Question

Explain the need for and importance of co-ordination?

Answered: 1 week ago

Question

Explain the contribution of Peter F. Drucker to Management .

Answered: 1 week ago