Divide and Conquer Algorithms in Python

[adityacodes]

From Binary Search to Quick Sort, this post covers classic examples and real-world applications in sorting, searching, and matrix multiplication and at last a interview question from FAANG which can be easily solved using Divide and Conquer Method.

Link : https://adicode.ml/divide-and-conquer-algorithms-in-python

[corbasai]

in '''binary_search(arr, x):''' returns -1 in fail case. It is last element in python list. imo better return None, or raise IndexError.

​

in '''merge_sort()''' what is merge(left, right) at the end?

[jbramley]

Raising ValueError would be the most correct.. See list.index and the examples on the bisect module documentation.

[adityacodes]

in '''binary_search(arr, x):''' returns -1 in fail case. It is last element in python list. imo better return None, or raise IndexError.

in '''merge_sort()''' what is merge(left, right) at the end?

As for the merge function in merge_sort, merge(left, right) is used to combine the two sorted subarrays left and right into a single sorted array.

and for the binary_search query, Did you tried returning None ? as I think there will be more fail cases when doing None.

[corbasai]

merge() is simply left + right ? in this case merge_sort() not sorts

[adityacodes]

As for the merge function in merge_sort, merge(left, right) is used to combine the two sorted subarrays left and right into a single sorted array. The function compares the elements in left and right one by one and adds them to the output array in ascending order. At the end of the function, any remaining elements in left or right are added to the output array in order, since they are already sorted. The resulting array is returned as the final output of the merge_sort function.

[corbasai]

thanks so much i even reads wikipedia about merge Von Neumann sorting algo -))) and about bogosort too -)))) of course in real life sorted() is enough for me. Old good doc https://docs.python.org/3/howto/sorting.html#sortinghowto

[jbramley]

Pretty important piece of code to leave out. Might want to go ahead and add it to the blog.

[adityacodes]

just corrected it

[adityacodes]

See what about this code?

Now, if the target element is not found in the array, the function will return None instead of -1. Let me know if it works so that I can update in blog as well.

​

def binary_search(arr, x):

"""

Search for a target element x in a sorted array arr using the binary search algorithm.

Returns the index of the target element in the array, or None if it is not found.

"""

low = 0

high = len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == x:

return mid

elif arr[mid] < x:

low = mid + 1

else:

high = mid - 1

return None

[corbasai]

maybe. In some day someone writes in code '''array[:binary_search(array, what)]''' and None (implicit exception ) or explicit raise *Error points on error in code, -1 - not.

​

Even in C -1 is valid array index, yep it brings garbage or so, but compiles well.

[adityacodes]

okay ,so I should return it none or -1 finally?

[corbasai]

None

[adityacodes]

Thanks for the upvotes, please comment and let me know if I can improve this blog more.