ActionScript 3.0 Design Patterns

A while back a comment by Timo Hannelin suggested that I use a skip list in one of the design patterns. (I looked but couldn’t find the comment, but I remember it was a good idea.) Anyway, I read the original article on skip lists by William Pugh. After reading the article and a few more articles on skip lists, I saw Timo’s point. However, since I’ve got my hands full with design patterns, and I dislike design pattern discussions degenerating into a chat about algorithms, I didn’t bring it up.

Algorithms in Participants

Having a little time right now, I thought I’d return to skip lists and see where they’d be valuable for participants in one of the design patterns. So, to warm up for working with skip lists I thought I’d whip up a Binary Search algorithm in ActionScript 3.0. Further, I wanted to entertain myself, and so I decided not to peek at any solutions on the Web.

After a few hours of trying to strong arm a solution I gave up and decided to peek. This is what I found:

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… — Professor Donald Knuth (Professor emeritus, Stanford University)

Further, I learned that only five out of twenty textbooks had accurate code for a binary search! Well, at least I didn’t feel like an idiot, but still, the concept is pretty simple, and it’s easy to do in your head. It’s just difficult (or tricky) to whip one up in code.

The Binary Search

The concept behind the binary search is to search by dividing an ordered list in consecutive halves. If the search guess is higher (in the ordered list) than the one being searched for, the bottom of a range is the search guess. If the search guess is lower; then the top of the range is the search guess. Each consecutive search is the halfway point between the top and bottom of the range. The solution is found by closing in like a vice taking chunks in halves rather than iterating through an entire list. It’s very fast and efficient for searches.

To get started, I created a function to generate a quick and dirty ordered array with 100 random numbers. (The variables were declared elsewhere in the class.)

1
2
3
4
5
6
7
8
9
10
11
12
13

private function generate():Array
{
	//Generates 100 numbers
	//Places them in a sorted array
	while (pack < 100)
	{
		ranInt=Math.random()*100;
		arrayPack.push(ranInt);
		pack++;
	}
	arrayPack.sort();
	return arrayPack;
}

Then I started writing the algorithm for the binary search. After locking up my computer with infinite loops a couple of times and rerouting the power grid of Bloomfield, Connecticut to Timbuktu, I gave up. Using numbers, I kept mixing up array numeric keys with the search values.

Your Turn to Have Some Fun

Anyway, since a lot of our readers like algorithms, I thought this might be a fun one for you to solve. You can find a lot of discussions of the binary search concept online as well as solutions (in the form of code and generic algorithms). However, see what you can come up with before you give up and peek (like I did). I can tell you this, though. One general solution uses recursive coding and the other uses iterative. Remember, though—only about a quarter of the computer science textbooks had it right. So, give it a go on your own knowing that if you come up with a solution, you’re smarter than 75% of the CS textbooks! We’ll use the Comments Section of this post for your solutions and look at skip lists in a future post.

No related posts.