1
I’m studying algorithms for Searching and wanted to better understand the difference between Binary search for ordered Binary search. I understood that for both algorithms to work, the list needs to be Sorted. From what I read in that question, this means that a list will always have a defined sequence based on the values of the elements. Thus, the code below (taken from a page of exercises on the subject) works with the line lista.sort(), but ceases to function (for both functions) if shooting it:
def Ordered_binary_Search(olist, item):
if len(olist) == 0:
return False
else:
midpoint = len(olist) // 2
if olist[midpoint] == item:
return True
else:
if item < olist[midpoint]:
return binarySearch(olist[:midpoint], item)
else:
return binarySearch(olist[midpoint+1:], item)
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
return found
lista=[0, 19, 52, 3, 1, 8, 14, 18, 34]
lista.sort()
print(binarySearch(lista, 3))
print(Ordered_binary_Search(lista, 3))
It occurs to me that the two functions are doing essentially the same thing. What it means ordered in that case? Is there any difference from Binary search to ordered Binary search?
I think it’s actually the same thing, and in this case, the difference is the implementation - see that the first uses recursion and the second, no. Maybe the
orderedin the name has been used to avoid a collision of names. As far as I know, so that a Binary search function, values passed to it must be in order (ordered). So it wouldn’t even make sense to create a unordered Binary search.– Luiz Felipe
For a Binary search to work on a list the list needs to be both ordered and Sorted? I understand why the list needs to be Sorted, but I don’t quite understand what it means to be ordered in this case and why this is necessary for the algorithm to work.
– Lucas
If you want to take the difference between "ordered" and "Sorted" literally (as you explain this answer), I believe the list should be Sorted, since the comparison criterion (which was used to draw lots the list) will be used in the Binary search to navigate between the "arms" of the "binary tree". In the case of your algorithm, note that the operator is being used
<. It requires that the list be ordered on a previously established criterion (in this case, from the smallest to the largest in numerical comparison). In short, Sorted.– Luiz Felipe
There is "binary search", and only. To me it just seems an unfortunate choice of name, because the function
Ordered_binary_Searchshould be calledrecursive_binary_searchbecause that’s what she does: the same thing as functionbinarySearch, but with recursion instead of iteration. Since the algorithm is the same, and the prerequisite of binary search is that the elements are sorted, this explains why pq only works if you sort the list first.– hkotsubo