|
How to Search an Array IntroductionThere 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. 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. Creating the ArrayTo 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 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. Linear SearchA 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. function linearSearch @pArray pItem # return 0 if we cannot find an item in the array # get the keys of the array # visit every array element indexed by a key # test if the current array element is a match with the item we are looking for 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. Logarithmic SearchA 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 # create a new range pointer that points to the item that lies # if we have found the matching item then stop processing and return it # if any of the range pointers have the same value # if we have not yet found a match and none of the range pointers have the same 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. |
Tweet
|