CISC 181 Lab 6 Implementing in JavaScript
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CISC 181
Lab 6
Implementing in JavaScript
As with the "coffee shop" lab, this lab will have you making some changes to a JavaScript program using a program editor such as Visual Studio Code. This time, however, you are going to be working from a pseudocode algorithm that you have seen before, that is, the one presented in the Algorithms unit for binary search, to implement the algorithm in JavaScript so that it works on real data.
Here is an algorithm for binary search in pseudocode. You will be referring to it a lot while you gradually turn it into JavaScript code that can be compiled and executed in your browser.
let n be the length of the list of numbers
let a be the list of numbers (a0, a1, a2, ..., an-1)
let val be number being searched for
let low be 0
let high be n - 1
while low ≤ high
let mid be floor((low + high)/2)
if amid = val
report position of val as mid
stop
if amid < val
set low to mid + 1
otherwise
set high to mid - 1
report val is not in the list
Something to keep in mind: The indenting in the pseudocode, above, is significant. It shows us which statements belong to the while loop, and which belong to the two if statements and to the otherwise statement. Importantly, it tells us that the report statement is not in the while loop. Your final JavaScript code should retain this indenting structure. It will help you (and a TA!) to spot potential problems in your code.
Since there are two levels of indenting in this pseudocode, your finished code should contain corresponding JavaScript blocks, each of which begins with a "{" curly bracket and ends with a "}" curly bracket. To make it more obvious where the blocks are, I have expanded my pseudocode below to include "{" and "}" block markers and made them bold so they are easier to see…
let n be the length of the list of numbers
let a be the list of numbers (a0, a1, a2, ..., an-1)
let val be number being searched for
let low be 0
let high be n - 1
while low ≤ high {
let mid be floor((low + high)/2)
if amid = val {
report position of val as mid
stop
}
if amid < val {
set low to mid + 1
}
otherwise {
set high to mid – 1
}
}
report val is not in the list
Refer to the above pseudocode frequently during this lab, as it accurately reflects the indenting and correct placement of the curly brackets in the JavaScript program you are about to create.
We're going to start with a big advantage: An existing program that demonstrates a linear search. It's in the Lab 06.zip file, stored as search.html, so extract it and open it in your text editor. It looks like this:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Search demo</title>
<script>
// Test lists
const word_list = ["dog", "duck", "frog", "rat", "tiger"];
const number_list = [-12, -7, 0, 4, 5, 10];
function find(a, val) {
// Return the position of val in array a, or the length
// of a if val is missing from a.
const n = a.length;
let i = 0;
while (i < n && a[i] != val) {
i = i + 1;
}
return i;
}
function report_result(a, val) {
const pos = find(a, val);
const list = a.join(", ");
if (pos < a.length) {
alert(val + " is at position " + pos + " in " + list + ".");
} else {
alert(val + " is not in " + list + ".");
}
}
// Test code
report_result (word_list, "cat"); // found
report_result (word_list, "cow"); // not found
report_result (word_list, "rat"); // found
report_result (number_list, 0); // found
report_result (number_list, 10); // found
report_result (number_list, -11); // not found
</script>
</head>
<body>
</body>
</html>
The first thing you should notice about this file is that it is a lot shorter than the beancounter.html file from the previous lab. Yay!
Drag the search.html file from a file listing onto an open browser so you can see how it looks when it is working. It just produces a series of pop-up alert messages showing where test values were (or were not) found in the test arrays.
From the code, you'll see that it uses two array variables, word_list, and number_list, to test its find function (the code in the middle). You can see other array variables being used in an example in the Programming Part 2 unit's slides. The object of this exercise is to change the code in the find function so instead of performing a linear search, as it does in its current form, it performs a binary search.
In the Algorithms unit, you learned that for a binary search to work, the data it is searching through must already be sorted. Happily, the six strings in the word_list array and the six values in the number_list array are already sorted! (If they weren't, we could apply the exchange sort algorithm to them to get them sorted.)
Before we start messing with the code, I'll explain a very little bit about how the current find function works. It does a linear search, as mentioned, 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 array 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
const 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 (subscript, 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 except for the comment lines at the top and leaving its opening and closing brace brackets in place.
function find(a, val) {
// Return the position of val in array a, or the length
// of a if val is missing from a.
}
Everything else you must do for this lab will go on new lines between the comments and the closing brace bracket, preserving the indenting structure of the pseudocode.
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. The Programming Part 1 unit's slides talked 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 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. Further note that the length of a doesn’t change in the binary search algorithm. That means your line declaring n, the first line inside those curly brackets, should be
const 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 for which the value won’t change. The next two variables in the function have values that may need to change, however, so these should be declared using the let keyword, not const.
· Declare and initialize the variables low and high, letting the pseudocode guide you as to what their initial values should be.
You should be ready to write your while loop. For guidance on the syntax, look at the while loop in the original, linear search 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! Next,
· 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.
Indented inside your while loop:
· Declare (with const since it will need to be set only once during each iteration of the while loop) 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 collection of mathematics tools called Math, and one of the functions it contains is called floor. Here's how you'd get the floor you're looking for:
Math.floor((low + high) / 2)
(Note the round brackets around the low + high. They're important!) So, when you are declaring your mid variable, initialize it with the expression I've given you above.
Next, the pseudocode has an if compound (multi-line) conditional statement. JavaScript has one of those, too, of course, and its syntax can be seen in the report_result function in the original code. The pseudocode doesn't call for an else part as is used in report_result, so you can ignore that for now. Anyway, continuing inside the while loop:
· Create the first and last lines of the first if statement with its opening and closing curly brackets. Like while, if requires a Boolean expression that must be enclosed in round brackets. To compare two values for equality in JavaScript, you don't use an equals sign, you use two of them together like this:
==
To write
amid
in JavaScript, you'd use this array notation
a[mid]
resulting in the complete Boolean expression:
a[mid] == val
Now we go inside the curly brackets of the if, indenting the contents another level as indicated in the pseudocode.
· The two statements in the pseudocode,
report position of val as mid
stop
get replaced with just one: a return of mid. See the syntax of the return statement in the original linear search version of the find function. We don't need the stop because a return statement causes a function to cease execution and returns control to whichever part of the program invoked the function.
Okay, that's the end of the first if statement, so move past its closing curly bracket and onto the second if statement. This one uses an otherwise clause in the pseudocode, and for that in JavaScript, you use else instead as you can see in the report_result function. So:
· Create your second if and an else (in place of the pseudocode's otherwise). If you've already declared a variable with let, don't use the let keyword with it again, just assign a new value to it as in
low = mid + 1;
Remember that the Boolean expression of the if (the else doesn't have or need one) needs to go in round brackets and your indenting should match the pseudocode. It's your choice if you write
} else {
or
}
else {
JavaScript doesn't care. (Neither do I! Some code styling is at the programmer's discretion.)
Nearly there, folks! All that's missing is a return statement, after the closing while curly bracket but BEFORE the closing function curly bracket. This is the return that needs to indicate to the rest of the program that val does not occur in the array, so the value returned should be, if you recall, the length of the array, a. And somewhere back a couple of pages is that information. So:
· Write the last statement of your find function. It returns the length of array a.
Save your work, then refresh your browser window to see if your program works. If it doesn't, you may have to close your browser window and open it again. Before you try running it a second time, check your code against the pseudocode first to see if you've missed anything.
This lab will be graded out of 15. For full marks, you must have a correct, working solution.
Create a new Lab 06 submission.zip file containing only your completed search.html file and submit it before the lab's deadline.
2022-10-21