How do I Search an Array?

This lesson describes two frequently used algorithms for finding entries in an array. Sample code is also provided.  

Introduction

There are a number of ways to search arrays and the choice of search depends largely on the type and size of the data set you are searching through. In particular, you may want to consider whether or not an array is to be sorted. A sorted array can significantly increase the speed with which you can search for an item in an array.

Refer to: How do I sort an array? for information on sorting arrays.

If an array is not sorted, your search algorithm will most likely have linear performance characteristics, and you would have to test every item in the array until you find the matching record. In the worst case scenario you would have to test every single item in the array. This is not necessarily a problem if the array is small or you run searches infrequently.

If you are using large data sets or you are searching for records on a frequent basis, then you may want to use a binary search algorithm that has logarithmic performance characteristics. This kind of algorithm is also called a boolean search and makes assumptions about how the data is stored in the array. These assumptions allow the search space to be halved at each iteration.

Creating the Array

To start with, we will create the array we want to search through. LiveCode arrays are associative arrays and store both a key and an entry. We can use this representation to sort the arrays or index the entries through the keys. In order to provide an array that works for both the linear and logarithmic searching algorithm, we order the content of the array alphabetically. You can test how the binary search algorithm starts to deteriorate when you start to change the order of the array.

# first we set up the entries in our array
local tArray
put "Adams, Alexander" into tArray[1]
put "Beaumont, Benjamin" into tArray[2]
put "Best, Tony" into tArray[3]
put "Case, Doreen" into tArray[4]
put "Frog, Diana" into tArray[5]
put "Kenyon, Oliver" into tArray[6]
put "Macphail, Ian" into tArray[7]
put "Miller, Kevin" into tArray[8]
put "Nobody, Peter" into tArray[9]
put "Pepe, Tio" into tArray[10]
put "Ralph, Sue" into tArray[11]
put "Scott, Peter" into tArray[12]
put "Ship, Steve" into tArray[13]
put "Smith, John" into tArray[14]
put "Walters, Chris" into tArray[15]

Note: The array key starts at 1 and increments by 1 for each new item that is added. It is important that you follow this numbering scheme for the binary search algorithm in this example to work. An item stored in array element 0 would not be found.

A Linear Search algorithm is an iterative process that tests one entry of the array at a time. In this case we start at the beginning of the array and compare every item in the array against the item we are searching for. The process stops once the item we were looking for has been found or all the array items have been tested and a match could not be found.

The worst case scenario for this algorithm is not finding a matching record. In this case it is necessary to step through the entire array and match against every single item. If we have 1024 items in the array, then we have to test all 1024 items to confirm that a match cannot be found.

function linearSearch @pArray pItem
	local tIndex
	local tResult
	# return 0 if we cannot find an item in the array
	put 0 into tResult
	# get the keys of the array
	get the keys of pArray
	split it by return
	# visit every array element indexed by a key
	repeat for each element tIndex in it
	# test if the current array element is a match with the item we are looking for 
		if pArray[tIndex] = pItem
		then
			put tIndex into tResult
			exit repeat
		end if      
	end repeat
	return tResult
end linearSearch

The function can be called as follows:

put linearSearch (tArray, "Best, Tony") into tArrayKey

The first argument to the function is the array we are searching through. This is passed in by reference only. The second argument is the item we are looking for. The result is the key that refers to the item of the array we matched against. This function returns 0 if no item is found. Remember how this ties in with the representation of the array where the keys start at 1.

A Logarithmic Search algorithm reduces the search area in the array by one half at each iteration. This provides significant performance advantages, compared to linear approaches. This performance is maintained, regardless if a match can be found in the array or not. If the array we are searching through had 1024 items, then the worst case scenario would only take 10 iterations to complete.

As the array is sorted, we compare our search item against the item that lies in the middle of the array and then test whether or not our item is greater or smaller than the item we are comparing it against. The result of this comparison allows us to discard half of the array items. So the first comparison would reduce the search space from 1024 items to 512. The second search would reduce the search space from 512 to 256 and so on, until we narrow our search down to one item that is or is not a match.

The algorithm in this example implements binary search using a programming technique referred to as recursion. Recursion means that the function can call itself from within itself. The variables in each instance of the call history are local to that instance of the function call. This allows us to break down the search space by a half, each time the binary search algorithm calls itself, without having to worry about keeping track of where exactly we are searching in the array.

function logarithmicSearch @pArray pItem pLeft pRight
	local tIndex
	local tResult
	# create a new range pointer that points to the item that lies
	#  right between the left and right range pointers
	put round ((pLeft + pRight) / 2) into tIndex
	# if we have found the matching item then stop processing and return it
	if pArray[tIndex] = pItem
	then put tIndex into tResult
	# if any of the range pointers have the same value
	# then the item we are looking for does not exist in the array and we return 0
	else if (pLeft = pRight or pLeft = tIndex or pRight = tIndex)
	then put 0 into tResult
	# if we have not yet found a match and none of the range pointers have the same
	# value then call logarithmicSearch again with a smaller search range
	# we are effectively halving the search area, each time we call logarithmicSearch
	else if pArray[tIndex] > pItem
	then put logarithmicSearch (pArray, pItem, pLeft, tIndex) into tResult
	else put logarithmicSearch (pArray, pItem, tIndex, pRight) into tResult
	end if
	return tResult
end logarithmicSearch

The function can be called as follows:

put logarithmicSearch (tSortedArray, "Best, Tony", 0, 15) into tArrayKey

The first argument to the function is the array we are searching through. We are passing this into the function by reference only. The second argument is the item we are looking for. The third and fourth arguments provide the array range we are searching through. The range starts with 0 and ends with 15. 0 is one less than the start key of the array and 15 is the last key of the array. The result is the value of the key that refers to the item of the array we matched against. This function returns 0 if no item is found. This ties in with the representation of the array when the keys start at 1.

Note: The reason for providing 0 as the starting point of the array is due to the way by which the array range is halved at each iteration. In this implementation we round the result of halving the array space. This means that we would never access an array item with a key of 0.

6 Comments

Jean-Paul

Thanks for this interresting lesson.
About the
I get an error compilation when trying to use your script with the last , just before .
When I avoid this script error compilation, the script run in an infinit loop.
Have you tried this script as is before ?

Jean-Paul

After some changes about the error compilation I mentionned earlyier, I apologise. This script runs.
Just one problem.
How can we manage the chars like "à,ù,é,î" etc. in an array?
I have used the just after the declaration var without success.

Thanks for your advice.

Juan

Can you try it with a bigger array and test every single key?

On my code I tested the LinearSearch for all the 35 elements on the array and it works perfectly.

I'm giving logarithmicSearch a try to see if it actually is faster, but it only works for a few elements. I sorted the array as mentioned in the "How do I sort an Array?" lesson.

Max

If I have to reorder and sort my array each time I modify it, what is the advantage of logarithmicSearch?

David

"Logarithmic search" is also commonly known as "binary search".

Test

This is is helpful but please put comment behind code not above the code so it's more helpful and understanding

Add your comment

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.