News for hackers. Stuff that matters.
Re:Binary Search Reconsidered (2018) by nomy99 on Friday December 25, 2020 @12:14PM (#25537633)
As soon as I read this I got paranoid and whipped one out, I am not sure if I missed edge cases

def binary_search(numbers: List[int], target: int) -> int:

    if not numbers:
        return -1
    if len(numbers) == 1 and numbers[0] != target:
        return -1

    middle = math.floor(len(numbers) / 2)

    if numbers[middle] == target:
        return target
    elif numbers[middle] > target:
        return binary_search(numbers[0: middle], target)
    else:
        return binary_search(numbers[middle + 1:], target)
Re:Binary Search Reconsidered (2018) by blackbear_ on Friday December 25, 2020 @02:02PM (#25538303)
Note that you're copying one half of the list into a new list at each recursive call, making the algorithm O(n). Better to pass the original list and use indices to indicate which portion you're working on
Re:Binary Search Reconsidered (2018) by tzs on Friday December 25, 2020 @03:31PM (#25538816)
Suppose he changed the type of numbers from List[int] to Tuple[int]. Would that get rid of the copying?

Tuples are immutable in Python, so in theory it should be able to but I have no idea if Python actually makes that optimization.

Even if it does, this is probably not a good approach in Python because Python does not optimize away tail recursion.

Re:Binary Search Reconsidered (2018) by zbentley on Friday December 25, 2020 @04:32PM (#25539200)
Python will reclaim/reuse tuples sometimes, but I'm unsure if it will fully "intern" them the way it does for ints (and java does for some strings).

Regardless, even if that optimization is present, the overhead of checking and deduping the tuples against the intern cache as they are constructed after the split operations would likely be considerable. Indexes would likely remain the very fastest strategy.

An optimization theoretically exists which could make tuple splitting as fast as index accounting (representing split results as slices/views into the original tuple), but I do not believe python does that, as it would cause unexpected memory growth in some situations, unless accompanied by a very specialized garbage collection scheme.

Re:Binary Search Reconsidered (2018) by nomy99 on Friday December 25, 2020 @02:05PM (#25538317)
great suggestion
Re:Binary Search Reconsidered (2018) by dan-robertson on Friday December 25, 2020 @12:25PM (#25537704)
The first error I spotted was on line 9.
Re:Binary Search Reconsidered (2018) by mark-r on Friday December 25, 2020 @03:10PM (#25538683)
Yeah, why worry about edge cases if you can't get the basic algorithm right?
Re:Binary Search Reconsidered (2018) by klyrs on Friday December 25, 2020 @07:04PM (#25540177)
Python is exceptionally bad at recursion. Binary search isn't the most egregious use case, as the call depth is logarithmic... but the call overhead is hefty and recursive algorithms are generally bad practice because of the low ceiling.
Re:Binary Search Reconsidered (2018) by mark-r on Friday December 25, 2020 @03:13PM (#25538703)
If you code this right, there's no need for the two special checks at the start of the function - they just naturally get resolved.