#6 - Functions and Binary Search

Welcome back to another adventure exploring the programming language Lisp.

This blog will cover:
-writing and using functions
-writing a binary search function

First let's look at the syntax for declaring a function:

We use: (defun functionName (parameters) (actions of the function) )

An example of a function that finds a the average of three values is below:

Now that we know how to use a function, we want to write a binary search function.
In order to do so, we need to know how to make an array in Lisp.

Syntax: (setf arrayName (make-array '(size)))

Then we use the aref function to refer to values in the array.  Which we need to do to set the value of each...
Setting value of first cell Syntax: (setf (aref arrayName cellNumber) value)

Example where we create a valArray and fill it with numbers in a random order:

Next we can write the binary search.  It will be a function that takes in a sorted array, and a value to search for as parameters.

To best examine the binary search, let's provide an example, then walkthrough the code in the example.

The function, binary-search, and the array.  I then loaded the array with even values from 2 to 16:
The array looks like this:
index : value
0 : 2
1 : 4
2 : 6
3 : 8
4 : 10
5 : 12
6 : 14
7 : 16

Then we when run the search we get:

This tells us that the value 12 that we looked for is at index 5 in the array, which is correct!

What is the function doing?
First, we use the let function to assign a low and high value, the low being 0 always, and high being the length of the array - 1.
Next we use a do loop to move the middle value in the array to narrow down the location of the value that we are looking for.
Finally, once we find the value, we can return the index of where the value is inside of the array.

Thanks for reading.

Peter Short, CS 270, Blog 6