I have just written a pseudo-code (actually in Python) of a binary search algorithm.
def binSearch(lst, number): left = 0 right = len(lst) - 1 while left <= right: middle = left + ((right - left) / 2) if number == lst[middle]: return True else: if number < lst[middle]: right = middle - 1 else: left = middle + 1 return False
It seems intuitively correct, but I'd like to use some stronger tool to be absolutely sure that my algorithm is correct.
I've read on Wikipedia, that I have to prove two things: Convergence (the algorithm will stop) and partial correctness (the algorithm will end with the right result). This is the proof of total correctness.
Could you demonstrate the proof of my binSearch
in theoretical computer science speech?
thank you