Or subtitled: Why turn down a chance to completely embarrass myself on the internet?
I read this post on Binary search on the Reinvigorated Programmer blog (In trying to learn more programming, I thought it wouldn’t hurt to read some programming blogs; plus as an unexpected bonus he likes Doctor Who) and thought I’d have a crack at it. However, the rules were a bit hard for me, namely:
“NO TESTING until after you’ve decided your program is correct.”
Even with Ruby, which I’m vaguely familiar with, I knew I couldn’t possibly write even the most basic program without resorting to trying out stuff in IRB. It’s the same as simple maths (times tables, etc) and spelling for me - I make no attempt to memorise this stuff when it’s easy to use a calculator, dictionary, etc. So that’s how my programming works. I can write a vague outline of the logic required in note form, but I need to use IRB or (if in another language) break my programme into chunks to compile and test, etc.
So, an honest a first attempt as possible (with just checking things like “How do ranges work in arrays again?” in IRB (told you it was embarrassing)) would be as follows:
First Attempt
#Assumes a pre-sorted array
def binsearch(array, target)
m = (array.length/2).floor #round down
until array[m] == target
#Find middle value of array
m = (array.length/2).floor #round down
puts m
#Which half contains target
if array[m] > target
#delete top half
array = array[0..m]
else
#delete bottom half
array = array[m..-1]
end
end
puts m
puts target
#Do we need to know where we found it?
end
This doesn’t work, the main problem being that I didn’t understand/forgot/didn’t-think-about-it-properly how the loop would check its condition. With m being updated at the start of the loop, it’s too late - the loop has begun so it’ll carry on and never break out of a loop.
Oh well, a bad first guess. At least with that out of the way I could try again, but this time I could test as I went along.
Second Attempt
def binsearch(array, target)
#Find middle index of array
m = (array.length/2).floor #round down
until array[m] == target
puts m
#Which half contains target
if array[m] > target
#delete top half
array = array[0..m]
else
#delete bottom half
array = array[m..-1]
end
m = (array.length/2).floor #round down
end
puts "Value found is " + array[m].to_s
puts "Target was " + target.to_s
#Do we need to know where we found it?
end
The main change is moving the update of m from top of loop to end. This got it basically working. I then decided (and I don’t think this is a requirement of the task set) to report out the index of the array where the result was found (because to me there didn’t seem to be a lot of point searching for something without knowing where it is).
Third attempt
def binsearch(array, target)
#Duplicate array so we have a copy of the original
orig = array.dup
#Find middle index of array
m = (array.length/2).floor #round down
#tracking index
tidx = m
until array[m] == target
puts "m= " + m.to_s
puts "tidx= " + tidx.to_s
#Which half contains target
if array[m] > target
#delete top half
array = array[0..m]
subtractidx = true
else
#delete bottom half
array = array[m+1..-1]
subtractidx = false
end
m = (array.length/2).floor
if subtractidx == true
tidx = tidx - m + 1
else
tidx = tidx + m + 1
end
end
puts "Value found is " + array[m].to_s
puts "Target was " + target.to_s
puts "Index of value is " + tidx.to_s
puts "Value at index is " + orig[tidx].to_s
end
I’d mucked up splitting the arrays and had overlapping ranges, 0..m and m..-1 so fixed that here as well. This attempt seemed to be working ok, but having accidentally seen a bit of the next post that dealt with common bugs in other people’s attempts at this problem, I knew there were things I’d not done: such as dealing with elements not in the array, etc. So that would be the next effort. Fair enough I wouldn’t have got this with my first “paper” attempt anyway, but I would have twigged pretty soon with testing (and as I said, testing is how I develop).
Fourth attempt:
def binsearch(array, target)
#Duplicate array so we have a copy of the original
orig = array.dup
found = true
#Find middle index of array
m = (array.length/2).floor #round down
#tracking index
tidx = m
until array[m] == target
puts "m= " + m.to_s
puts "tidx= " + tidx.to_s
#Which half contains target
if array[m] > target
#delete top half
array = array[0..m]
subtractidx = true
else
#delete bottom half
array = array[m+1..-1]
subtractidx = false
end
m = (array.length/2).floor
if subtractidx == true
tidx = tidx - m + 1
else
tidx = tidx + m + 1
end
if array.length == 1 and array[m] != target #if not found
found = false
break
end
end
puts found
if not found
puts "Value not found"
else
puts "Value found is " + array[m].to_s
puts "Target was " + target.to_s
puts "Index of value is " + tidx.to_s
puts "Value at index is " + orig[tidx].to_s
end
end
This still wasn’t completely right though. I.e. the index was not always right.
Fifth attempt
def binsearch(array, target)
#Duplicate array so we have a copy of the original
orig = array.dup
found = true
#Find middle index of array
m = (array.length/2)-1
#tracking index
tidx = m
until array[m] == target
puts array.to_s
puts "m= " + m.to_s
puts "tidx= " + tidx.to_s
#Which half contains target
if array[m] > target
#delete top half
array = array[0..m]
subtractidx = true
else
#delete bottom half
array = array[m+1..-1]
subtractidx = false
end
m = (array.length/2)-1
if subtractidx == true
tidx = tidx - m - 1
else
tidx = tidx + m
end
if array.length == 1 and array[m] != target #if not found
found = false
break
end
end
puts found
if not found
puts "Value not found"
else
puts array.to_s
puts "m= " + m.to_s
puts "tidx= " + tidx.to_s
puts "Value found is " + array[m].to_s
puts "Target was " + target.to_s
puts "Index of value is " + tidx.to_s
puts "Value at index is " + orig[tidx].to_s
end
end
Trying to get the index correct, but still crap. I did discover though that I didn’t need the floor method to round down, as that was happening anyway (see, further embarrassment). Decided to give up figuring this (index tracking) out. Must be a simpler way. Rather than split the array up, just change the range we are looking at:
Sixth (and final-ish) attempt
def binsearch(array, target)
#Assume search suceeds
found = true
#initial lower, upper and middle indexes
l = 0
u = array.length-1
m = (u-l)/2
until array[m] == target
#Visualise the search
puts array[l..u].to_s
puts "l= " + l.to_s
puts "m= " + m.to_s
puts "u= " + u.to_s
#Which half contains target?
if array[m] > target
u = m #Set new upper boundary
else
l = m + 1 #set new lower boundary
end
m = (u-l)/2+l #set new mid point
#Break if not found / out-of-range
if l==u and array[m] != target
found = false
break
end
end
#Visualise search
puts array[l..u].to_s
puts "l= " + l.to_s
puts "m= " + m.to_s
puts "u= " + u.to_s
if not found
puts "Value not found"
else
puts "Value found is " + array[m].to_s
puts "Target was " + target.to_s
puts "Index found at is " + m.to_s
end
end
Ok, so pretty happy with that. Seems to work ok. It’s longer than it needs to be thanks to all the puts statements, but I like seeing how it arrives at the solution. Seems to find values, return correct indexes, deal with values not in the array. But what about single element or zero element arrays (also accidentally peeked at)? Whoops no good.
e.g.
binsearch([0], 1)
binsearch([-1], 1)
binsearch([-1], 0)
all just loop continuously, and
binsearch([], 1)
throws an error.
Zero length arrays are not such a worry, easy to check for that up front (even for me!), but the single element one going into a continuous loop is a more of a concern. A crappy, but simple fix would be:
if array.length == 1
if array[0] == target
#Joy to the world
else
#Best stop things now
break
end
end
But I’m sure there is a more elegant way?
Finally
I’d like to be able to use a get out clause:
I am confident that nearly everyone who reads this blog is already familiar with the binary search algorithm
and say “Well, nope I’m not familiar”, which I’m not, but I did understand the principle of the search. Really this just harks back to school Maths (which was a while ago for me) and iterative searches, etc. “Binary Search” is just different terminology. So no excuse really - I should have been able to figure it out. Perhaps what I should have done was forget the programming language aspect and just write it down logically/mathematically. Ah well, eager beaver and that.
Guess I have a long way to go yet if I want to be a programmer.