0

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
greybeard
  • 2,102
  • 7
  • 24
  • 58
Samiun Black
  • 1
  • 2
    Specifying what you mean by "better" may help others answer your question. Better in terms of performance? Or readability? Or some other measure of performance? – J. Lee Jan 01 '22 at 08:23
  • https://stackoverflow.com/questions/39416560/how-can-i-simplify-this-working-binary-search-code-in-c/39417165#39417165 – Matt Timmermans Jan 01 '22 at 14:56
  • (Your `xyzVal`s are indexes, not values. Then, there is the [Style Guide for Python Code](https://www.python.org/dev/peps/pep-0008/#function-and-variable-names).) – greybeard Jan 01 '22 at 16:26
  • How did you test the code presented? – greybeard Jan 01 '22 at 16:27

2 Answers2

1

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.

trincot
  • 263,463
  • 30
  • 215
  • 251
0

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.

Chris
  • 109
  • 8