5 ms·
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:
by nomy99 6y ago
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)
- blackbear_ 6y agoNote 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
- nomy99 6y agogreat suggestion
- tzs 6y agoSuppose 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.
- zbentley 6y agoPython 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.
- deleted 6y ago[deleted]
- dan-robertson 6y agoThe first error I spotted was on line 9.
- mark-r 6y agoYeah, why worry about edge cases if you can't get the basic algorithm right?
- mark-r 6y agoIf you code this right, there's no need for the two special checks at the start of the function - they just naturally get resolved.
- klyrs 6y agoPython 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.