ActionScript 3.0 Design Patterns

The Recursive Vice

After our post on the binary search algorithm, I found that no one had cooked up an example of a Recursive Binary Search. So, I did. In a recent post, we looked at linked lists and used a recursive algorithm to move through the list. The algorithm is simple, and I hope explains both binary search and how to use recursion with such a search. As with the other posts in this recent series, we’re working our way to skip lists, and I hope this will aid in understanding how skip lists work.

Divide and Conquer

The binary search algorithm uses a divide and conquer approach that works like a vice. With each division in half, the bottom range gets higher and the top range gets lower and the search object is either squeezed out or not found. This saves a lot of poking around an array (or other list) to find what you’re looking for.

When using recursion, the function containing the search algorithm keeps calling itself until a match occurs or it runs out of places to look. In order to provide a visual representation of what’s going on, I used trace statements with each call to a recursive function. As you will see, with each recursive call, the search function displays the call and the values. The first parameter is the search value (44 in this case) and the second two parameters represent the beginning and ending values of the search fields. When you run the program, you will see something like the following:

recursive call to: recursiveBinarySearch(44,0,49);
recursive call to: recursiveBinarySearch(44,25,49);
recursive call to: recursiveBinarySearch(44,38,49);
recursive call to: recursiveBinarySearch(44,38,42);
recursive call to: recursiveBinarySearch(44,41,42);
recursive call to: recursiveBinarySearch(44,42,42);
Your number is at position 42

The beginning search of 100 elements is 49 for the top and 0 for the bottom. It then moves up through the numeric elements of the array until it finally squeezes out the found item in array element 42. (The array is randomly populated from 1 to 100 and then sorted—binary searches require sorted lists.)

Normally in these posts I don’t use a lot of comments in the code because the text in the post is supposed to explain everything. (Also, comments often get in the way of the flow of the programming logic and good agile programming shouldn’t need comments.) However, for this algorithm, I found that it probably helps to see each step in detail so I put in quite a few comments.

I also put the algorithm in a class. Because,

…an algorithm without a class is like a child without a mother…

That reminds me, Happy Mothers Day to all of you mothers out there.

(I suppose a corollary would be,

…a class without a design pattern is like a child without a father…

but I’d never say that because people might get the wrong idea about the latter piece of wisdom.)

Okay, so let’s take a look at the class containing the algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

package
{
	import flash.display.Sprite;
 
	public class Binary extends Sprite
	{
		private var searchArray:Array=new Array();
		private var sizeNow:int;
		private var mid:int;
		private var poke:int;
		private var begin:int;
		private var end:int;
		private var flagUp:Boolean=true;
 
		public function Binary()
		{
			for (var stuff:int=0; stuff<100; stuff++)
			{
				searchArray.push(int(Math.random()*100));
			}
			searchArray.sort();
			sizeNow=searchArray.length;
		}
 
		public function recursiveBinarySearch(valueN:int,begin:int,end:int):int
		{
			/*Only on the first time through use the array
			length as the end value. The Algorithm keeps
			changing the end value so you don't want to use
			the array length more than once.    */
			if (flagUp)
			{
				end=sizeNow;
				flagUp=false;
			}
 
			/*If the end value is smaller than the begin value
			the search is over and item was not found.    */
			if (end<begin)
			{
				return -1;
			}
 
			/*Find the midway point between begin and end
			and use it as the numeric key for the current search
			value—guess (poke).     */
			mid=int((begin + end)/2);
			poke=searchArray[mid];
 
			/*If a match occurs return
			the value of the numeric key.  Search ends here.  */
			if (poke==valueN)
			{
				return mid;
			}
 
			/*If no match; guess larger than value; the end value
			becomes the midway value minus 1. Otherwise, the begin
			value becomes the midway value plus 1.     */
			else
			{
				if (poke>valueN)
				{
					end=mid-1;
				}
				else
				{
					if (poke<valueN)
					{
						begin=mid+1;
					}
				}
			}
 
			/* Keep making the recursive call until value is found
			or all possible values are searched */
			trace("recursive call to: recursiveBinarySearch("+valueN+","+begin+","+end+");");
			return recursiveBinarySearch(valueN,begin,end);
		}
	}
}

Like I said, there are a lot of comments there so that you can see the steps through the algorithm. Now, a second class acts like a client and calls the method in the Binary class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

package
{
	import flash.display.Sprite;
	public class Searcher extends Sprite
	{
		private var searching:Binary=new Binary();
		private var searchElement:Number;
		private var searchNow:Number;
 
		public function Searcher()
		{
			searchNow=searching.recursiveBinarySearch(44,0,0);
			if (searchNow>=0 && searchNow != 4294967295)
			{
				trace("Your number is at position " + searchNow );
			}
			else
			{
				trace("Not found");
			}
		}
	}
}

Keep in mind that all of the searches are searching the numeric element keys of the array—not the values. Therefore, you shouldn’t expect the found value to be the same as the numeric key value. Also, since the values are generated randomly, the value you place in the first parameter of the line:

searchNow=searching.recursiveBinarySearch(44,0,0);

may not be found at all. I put in 44 for the search value, but you can add any value you want between 1 and 100. Alternatively, you can fix it up so that you can dynamically enter different values or even change it to make it look for string values. However, the point is simply to demonstrate how to create and use a recursive binary search.

As always, your comments, corrections and wisdom are always welcomed.

Related posts:

1. A Funny Thing Happened on the way to Skip Lists: The ActionScript 3.0 Binary Search Algorithm