I have tried to implement a binary search algorithm by myself in python and it worked but when I looked into the internet most of them did differently. I don't know which one is better from these two
My Binary Search Algorithm
def binary_search(arr, item):
minVal = 0
maxVal = len(arr) - 1
backtrack = 0
while (True):
midPosition = (maxVal - minVal)//2 backtrack
mid = arr[midPosition]
if mid > item:
maxVal = midPosition
backtrack = midPosition
elif mid < item:
minVal = midPosition
backtrack = midPosition
else:
print(midPosition)
break
Tutorial's binary search algorithm
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high low) // 2
# If x is greater, ignore left half
if arr[mid] < x:
low = mid 1
# If x is smaller, ignore right half
elif arr[mid] > x:
high = mid - 1
# means x is present at mid
else:
return mid
# If we reach here, then the element was not present
return -1
CodePudding user response:
While both algorithms are basically the same (they need the same amount of iterations), the first one is a little bit slower since you have an additional assignment. The addition/subtraction in the second code is most likely always cheaper.
CodePudding user response:
Your algorithm is not correct.
For instance, this call will lead to an infinite loop:
binary_search([1,2,3], 3)
But also, your code has no provision for when the searched value is not in the list, and also then the loop will continue forever.
Reasons for these issues:
First of all, the backtrack
value should always be minVal
. And for that reason you would no longer benefit from this extra variable.
Secondly, when you narrow down the search "window", you should exclude the mid
index from that new window.
Finally, such a function should not print the result, but return it. That is essential for making your function reusable, as it allows the caller to store the result in a variable instead of printing it.
Correction
In order to make your code work, it should look like this:
def binary_search(arr, item):
minVal = 0
maxVal = len(arr) - 1
while minVal <= maxVal: # stop when window is empty
# must always add minVal
midPosition = (maxVal - minVal)//2 minVal
mid = arr[midPosition]
if mid > item:
# exclude midPosition from new window
maxVal = midPosition - 1
elif mid < item:
# exclude midPosition from new window
minVal = midPosition 1
else:
return midPosition # don't print
return -1 # not found
And now your function is almost the same as the one you found elsewhere. The following formulas are mathematically equivalent:
(maxVal - minVal)//2 minVal
(maxVal minVal)//2
In Python there is no reason to choose the longer one.