[godelski]

This makes for an interesting test. I checked Claude Sonnet, just for the he'll of it

  Prompt:
  Please write a bug free binary search in python

  Answer:
  def binary_search(arr, target):
    """
    Performs binary search on a sorted array.
  
    Args:
        arr: A sorted list of comparable elements
        target: The element to search for
  
    Returns:
        The index of target if found, -1 otherwise
    """
    left = 0
    right = len(arr) - 1
  
    while left <= right:
        # Avoid potential overflow by using this formula
        mid = left + (right - left) // 2
      
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
  
    return -1

# Example usage and test cases if __name__ == "__main__": # Test cases test_array = [1, 3, 5, 7, 9, 11, 13, 15]

    print(binary_search(test_array, 7))    # Output: 3
    print(binary_search(test_array, 1))    # Output: 0
    print(binary_search(test_array, 15))   # Output: 7
    print(binary_search(test_array, 4))    # Output: -1
    print(binary_search([], 5))            # Output: -1
    print(binary_search([5], 5))           # Output: 0
    print(binary_search([5], 3))           # Output: -1

[hiAndrewQuinn]

Very good! Looks good to me. One small callout:

        mid = left + (right - left) // 2

This implementation detail is to my knowledge unnecessary in Python because Python's built-in int type has arbitrary-precision integers. It's intended to avoid buffer overflows in languages like C.

Imagine, say, that left is 1 and right is 2^63 - 1. In Python left + right will just give you 2^63, no big deal. In C, left + right will overflow and produce undefined behavior; in practice it usually gives you I think -2^63, which is obviously going to screw up the bsearch a bit. It isn't wrong, just slightly less idiomatic for the language.

Python's interpreter may or may not be able to recognize and refactor the slight inefficiency of the extra arithmetic operation out. I will only point out that most of the time when we write our own bsearch it's because we want to optimize something really fundamental to the codebase. Any time you have to whip up your own algorithm it's prima facie evidence that that part of the code might be good to profile.

[naniwaduni]

Even in languages like C, it's mostly voodoo in practice unless you're using undersized indices anyway—you surely don't have anywhere near SIZE_MAX/2 elements.

The underlying problem is sloppy use of int for indices. The roundabout calculation will still overflow at twice the size.

[namibj]

For scalar code that's fair, but keep in mind that with `gather`, you can vectorize it, and there you do worry about integer width as more width means fewer lanes. Though tbf you probably should use B+ Tree structures chunked to your bulk/cache fetch "line/page" size, and vectorized higher-than-radix-2 search within each node.

[inhumantsar]

IIRC you're correct, but the comment is a red herring.

In Python, the double slash (or type casting) is necessary as a single slash will yield a float by default. Double slash returns an int.