week of march 12, 2014 csc148h1 winter 2014

Topic(s): binary search
Assume a list in already-sorted order.
If you were asked to find a value within the list, how would you do it?
The simplest way would be to iterate through every single value in the list and check each value and return iff there is a value that match.
The question now becomes: how efficient is that?
If you were given a ridiculously long list and the target value is near the end of that ridiculously long list, that would take forever to such a point that you would doubt if your code will ever terminate.
There does exist a faster way of retrieving that value (providing that the list is sorted in order) - binary search.
The though process of it is that: assume the list in sorted order, you find the middle most value of the list, if the middle value is not the target value, you check whether it is bigger or smaller than the target value and ignore the other half of the list. The same process is recursed with the now half-sized list - find middle most value, if it != the target value, begin again on the half that contains the target value.
The complexity of this search sequence pays off in terms of time efficiency since the computer is only working with (1/2)^n of the content at all times.