Sequential Searches (or Linear Searches) are the simplest form of searching you could think of: start from one side of a list and go to the other side, checking each element to see if your target shows up. It's not very efficient, for example if I have a list of one million items and I'm looking for the element 19102348 (perhaps this is a phone number list) and it happens to be one the opposite side of the list to where I start searching, I'm in for a good time. The only real benefit to sequential searches other than their simplicity is their ability to take a list of any form and find the desired element without messing around with anything.
Binary Searches are more efficient than sequential searches but do indeed do some messing around (note the tactical insertion of the word 'indeed' to avoid saying do do). A binary search only works on sorted lists because its method is dependent on telling whether the target is higher or lower in the list than the element that the search is inspecting. The idea is to begin by selecting the middle element in the list so if the length of the list is n, the item's index will be (n-1)/2 and it'll need to be floored to ensure you don't go looking for an index of 8.5 or something (i.e. to ensure nothing goes wrong if your list has an odd number of elements). So you look at this middle element and determine whether it's larger or smaller than your target. If it's larger, clearly you don't need to bother looking to the right of the element (assuming the list is in ascending order) so you can just focus on the left hand side.
So you now want to treat this new left-hand section of the list as a list in and of itself. You can store a value called 'high' or something which is the highest index in the list (previously it would have been n-1). And now we want it to be one less than the index you just checked (because that index and all those to the right of it were larger than the target). If we're going to have an upper bound variable it makes sense to have a lower bound one too (call it 'low') incase for example the target was larger than the first element we checked and the new list had the same upper bound but the lower bound needed to be changed to 1 greater than the element we checked.
Alright so now the lower bound will be 0 (nothing's changed here) and the upper bound will be ⌊(n-1)/2⌋-1. Now we just repeat the process we did at the beginning; compare the middle element of this section of the list to the target. So the middle (we can call the variable 'mid') will be ⌊(high+low)/2⌋. If the element is the target, we can return its index. If it's larger than the target, we need to look to the left meaning we need to set the upper bound to the middle element's index minus 1 and if it's smaller than the target we need to bring the lower bound to the middle element's index plus 1.
We can repeat the process until the target is found, in which case we return the index of that element. We also need to account for the possibility that the target isn't in the list. Eventually we'll get low = high at some point i.e. there's only one element in our sublist and after the algorithm checks that, if the element isn't the target and it's smaller than the target, low will end up being low+1 and if it's greater than the target, high will end up being high-1. In either case, high will end up lower than low (where in all other circumstances high > low) and it's at that point we can say the algorithm failed to find the target and return -1 (which is the all-encompassing 'I have failed you' return value).
I'll be making a big recursion post later on but for now, we can just say that a recursive function is one which calls itself with slightly modified input.
Let's say our algorithm is called BinarySearch and it takes the arguments 'list' (our list will be called L), 'target' (i.e. the target value), 'low', and 'high'. Our list L will have n elements and thus we can initialise low = 0 and high = n-1. Here's the pseudocode for the algorithm:
Clearly this algorithm will be repeating the same process again and again but on smaller sections of the list (with the range of each section defined by low to high) which begs the question of what kind of algorithm to use. When you find that through your algorithm you create smaller problems similar to the original problem that needed to be solved, recursion is a useful tool to use.
BinarySearch(L, target, low, high) {
if (high < low)
return -1
mid = ⌊(low + high) / 2⌋
if (target < L[mid])
return BinarySearch(L, target, low, mid-1) //consider left half
else if (target > L[mid])
return BinarySearch(L, target, mid+1, high) //consider right half
else //the only other possibility is for target = L[mid] in which case y //you've found your target and can return the index of it i.e. mid.
return mid
}
Let's see what happens with a list like L=[1,4,6,8,9,10,12,15,19,24,30] (it's got 11 elements) when searching for 9. We call the algorithm:
BinarySearch(L, 9, 0, length(L)-1)
First it checks whether high < low i.e. whether 10<0 which it's not so we move on to the initialisation of mid. mid will be ⌊(10+0)/2⌋ = 5 so we're looking at the element with index 5, which is the 10 in the list. Now we see whether the target is less than 10 and it is because we're searching for 9 so we call the algorithm again but now it's:
BinarySearch(L, 9, low, mid-1) where mid-1 is 4 and low is still 0.
We do the high < low check again and it's false again because there's still a chance we can find our target, then we get the new mid which will be ⌊(4+0)/2⌋ which is 2 (referring to the 6 in the list) and now we check whether it's larger than the target and it's not and then we check whether it's smaller than the target and it is so we now only care about the elements between the elements 6 and 10 exclusive. So we call the algorithm again:
BinarySearch(L, 9, mid+1, high) where mid+1 is 3 (referring to the 8 in the list) and high is unchanged since the last call i.e. 4 (referring to the 9 in the list).
We go through again and find out the mid is ⌊(4+3)/2⌋ = 3. The target is higher than this so look to the right by bringing low up to mid+1 which is 4. Again we call the algorithm:
BinarySearch(L, 9, mid+1, high) where mid+1 is 4 and high is also 4 so we've got 1 element left.
The one element we have left is 9 (index = 4) which is luckily the target so the algorithm sets the new mid to ⌊(4+4)/2⌋ = 4 and after working out that the target is neither smaller nor larger than the 9 in the list, it can say 'aha! found it' and then return the index of 4 i.e. 'the element you're looking for has the index of 4 in the list'.
However we're not done because this BinarySearch algorithm is going to return that result to the algorithm which called it and then that algorithm, having now a value to return to the algorithm that called it, can do so and the chain continues all the way back to the very first algorithm we called which then directly returns the index to us. When you have a recursive algorithm whose last action is returning the result of another instance of the same algorithm (which is what we're dealing with here) we call that algorithm 'tail recursive' because the recursion occurs at the 'tail' (i.e. at the end) of the algorithm. This doesn't mean the end as in the last line of code in the algorithm but the last action it performs (for example either of the two BinarySeach calls in the BinarySearch algorithm can be at the tail of the algorithm depending on whichever is called).
Now recursive algorithms are useful in being fairly intuitive to use and often simplistic but in every single case of using a recursive algorithm, an iterative algorithm could be used instead. This is because the recursive algorithms are handled by the CPU as iterative anyway with the assistance of a call stack (I'll write about that later).
The iterative approach to the BinarySearch algorithm is as follows:
BinarySearch(L, target) {
low = 0
high = length(L) - 1
while ⌊(low <= high)⌋ { mid = (low + high) / 2
if (target < L[mid])
high = mid - 1
else if (target > L[mid])
low = mid + 1
else
return mid
}
return -1
}
luckily for us, this is an instance where an iterative algorithm is a whole lot simpler than wrapping one's head around the recursive alternative. Having said that, the binary search was a good place to warm up for all the recursive algorithms to come
Let's see what happens with a list like L=[1,4,6,8,9,10,12,15,19,24,30] (it's got 11 elements) when searching for 9. We call the algorithm:
BinarySearch(L, 9, 0, length(L)-1)
First it checks whether high < low i.e. whether 10<0 which it's not so we move on to the initialisation of mid. mid will be ⌊(10+0)/2⌋ = 5 so we're looking at the element with index 5, which is the 10 in the list. Now we see whether the target is less than 10 and it is because we're searching for 9 so we call the algorithm again but now it's:
BinarySearch(L, 9, low, mid-1) where mid-1 is 4 and low is still 0.
We do the high < low check again and it's false again because there's still a chance we can find our target, then we get the new mid which will be ⌊(4+0)/2⌋ which is 2 (referring to the 6 in the list) and now we check whether it's larger than the target and it's not and then we check whether it's smaller than the target and it is so we now only care about the elements between the elements 6 and 10 exclusive. So we call the algorithm again:
BinarySearch(L, 9, mid+1, high) where mid+1 is 3 (referring to the 8 in the list) and high is unchanged since the last call i.e. 4 (referring to the 9 in the list).
We go through again and find out the mid is ⌊(4+3)/2⌋ = 3. The target is higher than this so look to the right by bringing low up to mid+1 which is 4. Again we call the algorithm:
BinarySearch(L, 9, mid+1, high) where mid+1 is 4 and high is also 4 so we've got 1 element left.
The one element we have left is 9 (index = 4) which is luckily the target so the algorithm sets the new mid to ⌊(4+4)/2⌋ = 4 and after working out that the target is neither smaller nor larger than the 9 in the list, it can say 'aha! found it' and then return the index of 4 i.e. 'the element you're looking for has the index of 4 in the list'.
However we're not done because this BinarySearch algorithm is going to return that result to the algorithm which called it and then that algorithm, having now a value to return to the algorithm that called it, can do so and the chain continues all the way back to the very first algorithm we called which then directly returns the index to us. When you have a recursive algorithm whose last action is returning the result of another instance of the same algorithm (which is what we're dealing with here) we call that algorithm 'tail recursive' because the recursion occurs at the 'tail' (i.e. at the end) of the algorithm. This doesn't mean the end as in the last line of code in the algorithm but the last action it performs (for example either of the two BinarySeach calls in the BinarySearch algorithm can be at the tail of the algorithm depending on whichever is called).
Now recursive algorithms are useful in being fairly intuitive to use and often simplistic but in every single case of using a recursive algorithm, an iterative algorithm could be used instead. This is because the recursive algorithms are handled by the CPU as iterative anyway with the assistance of a call stack (I'll write about that later).
The iterative approach to the BinarySearch algorithm is as follows:
BinarySearch(L, target) {
low = 0
high = length(L) - 1
while ⌊(low <= high)⌋ { mid = (low + high) / 2
if (target < L[mid])
high = mid - 1
else if (target > L[mid])
low = mid + 1
else
return mid
}
return -1
}
luckily for us, this is an instance where an iterative algorithm is a whole lot simpler than wrapping one's head around the recursive alternative. Having said that, the binary search was a good place to warm up for all the recursive algorithms to come
No comments:
Post a Comment