Binary Search

cf. Binary Search

Given a sorted array arr[], of n elements, write a function to search a given element x in arr[]


In [19]:
def binarySearch(arr,l,r,x):
    """ 
        @details denote L = len(arr)
        @param indices l,r=0,1...L-1
        @note l <= r expected
        base case is if l>r, then stop, nothing was found 
    """
    if (r<l):
        return -1 # x was not found

    else:
        mid = l + (r-l)/2
        
        if arr[mid] == x: # found it, success!  
            return mid
        # if arr[mid] > x, then we know x is "to the left" of mid
        elif arr[mid]> x:
            r = mid-1
            return binarySearch(arr,l,r,x)
        else: # then we know x is "to the right" of mid
            l=mid+1
            return binarySearch(arr,l,r,x)

In [20]:
arr=[2,3,4,10,40]

In [21]:
x=10

In [22]:
result=binarySearch(arr,0,len(arr)-1,x)
print(result)


3

In [23]:
# Returns index of x in arr if present, else -1
def binarySearch (arr, l, r, x):
 
    # Check base case
    if r >= l:
 
        mid = l + (r - l)/2
 
        # If element is present at the middle itself
        if arr[mid] == x:
            return mid
         
        # If element is smaller than mid, then it can only
        # be present in left subarray
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
 
        # Else the element can only be present in right subarray
        else:
            return binarySearch(arr, mid+1, r, x)
 
    else:
        # Element is not present in the array
        return -1

In [25]:
def binarySearch_iter(arr,l,r,x):
    while (l<=r):
        mid = l + (r-l)/2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x: # x is "to the left" of mid and it's not at mid
            r = mid-1
        else: # x is "to the right" of mid and it's not mid
            l=mid+1
        
    return -1 # x was not found at all

In [26]:
print(binarySearch_iter(arr,0,len(arr)-1,x))


3

Time complexity, time complexity of Binary Search is $T(n) = T(n/2)+c$, above recurrence can be solved using Recurrence, $O(\log{n})$.

Merge Sort

http://www.geeksforgeeks.org/merge-sort/

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html

base case is sublist contains only 1 item or is empty.

If list has more than 1 item, split list and recursively invoke a merge sort on both halves.

Merging is the process of taking 2 smaller sorted lists and combining them together into a single sorted, new list.


In [39]:
def mergeSort(arr):
    print("splitting",arr)
    if len(arr) > 1: # then we continue to split
        mid = len(arr) // 2
        l_arr=arr[:mid] # left half of arr
        r_arr = arr[mid:] # right half of arr
        
        mergeSort(l_arr)
        mergeSort(r_arr)
        
        # now difficult part; how do we "blend" or merge together 2 sorted halves into 1 sorted list?
        i=0 # index for l_arr, i=0,1...len(l_arr)-1
        j=0 # index for r_arr, j=0,1...len(r_arr)-1
        k=0 # index for arr,   k=0,1...len(arr)-1
        while i<len(l_arr) and j < len(r_arr):
            if l_arr[i] < r_arr[j]: # so l_arr into arr, and increment l_arr's index, i 
                arr[k] = l_arr[i]
                i+=1 
            else:
                arr[k] = r_arr[j]
                j+=1
            k=k+1
        # then deal with "leftovers"
        while i < len(l_arr):
            arr[k] = l_arr[i]
            i+=1
            k+=1
        
        while j < len(r_arr):
            arr[k] = r_arr[j]
            j+=1
            k+=1
    print("Merging",arr)
#    return arr

In [40]:
alist = [54,26,93,17,77,31,44,55,20]
#alist_1 = mergeSort(alist)
mergeSort(alist)


('splitting', [54, 26, 93, 17, 77, 31, 44, 55, 20])
('splitting', [54, 26, 93, 17])
('splitting', [54, 26])
('splitting', [54])
('Merging', [54])
('splitting', [26])
('Merging', [26])
('Merging', [26, 54])
('splitting', [93, 17])
('splitting', [93])
('Merging', [93])
('splitting', [17])
('Merging', [17])
('Merging', [17, 93])
('Merging', [17, 26, 54, 93])
('splitting', [77, 31, 44, 55, 20])
('splitting', [77, 31])
('splitting', [77])
('Merging', [77])
('splitting', [31])
('Merging', [31])
('Merging', [31, 77])
('splitting', [44, 55, 20])
('splitting', [44])
('Merging', [44])
('splitting', [55, 20])
('splitting', [55])
('Merging', [55])
('splitting', [20])
('Merging', [20])
('Merging', [20, 55])
('Merging', [20, 44, 55])
('Merging', [20, 31, 44, 55, 77])
('Merging', [17, 20, 26, 31, 44, 54, 55, 77, 93])

In [35]:
alist


Out[35]:
[17, 20, 55, 44, 31, 77, 93, 26, 54]

In [36]:
def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

In [37]:
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)


('Splitting ', [54, 26, 93, 17, 77, 31, 44, 55, 20])
('Splitting ', [54, 26, 93, 17])
('Splitting ', [54, 26])
('Splitting ', [54])
('Merging ', [54])
('Splitting ', [26])
('Merging ', [26])
('Merging ', [26, 54])
('Splitting ', [93, 17])
('Splitting ', [93])
('Merging ', [93])
('Splitting ', [17])
('Merging ', [17])
('Merging ', [17, 93])
('Merging ', [17, 26, 54, 93])
('Splitting ', [77, 31, 44, 55, 20])
('Splitting ', [77, 31])
('Splitting ', [77])
('Merging ', [77])
('Splitting ', [31])
('Merging ', [31])
('Merging ', [31, 77])
('Splitting ', [44, 55, 20])
('Splitting ', [44])
('Merging ', [44])
('Splitting ', [55, 20])
('Splitting ', [55])
('Merging ', [55])
('Splitting ', [20])
('Merging ', [20])
('Merging ', [20, 55])
('Merging ', [20, 44, 55])
('Merging ', [20, 31, 44, 55, 77])
('Merging ', [17, 20, 26, 31, 44, 54, 55, 77, 93])
[17, 20, 26, 31, 44, 54, 55, 77, 93]

Quick Sort


In [42]:
def quickSort(arr,l,r):
    if l < r:
        ip = partition(arr,l,r)
        
        quickSort(arr,l,ip-1)
        quickSort(arr,ip+1,r)
        
def partition(arr,l,r):
    # the goal of the partition process is to move items that are on the wrong side 
    # with respect to the pivot value, while also converging on the split point
    i = (l-1) # index of smaller element
    pivot = arr[r]
    
    for j in range(l,r):
        if arr[j]<= pivot:
            i +=1 # increment smaller element
            arr[i],arr[j] = arr[j],arr[i] # swap
    arr[i+1],arr[r] = arr[r],arr[i+1]  # position of i+1 is now the split point, 
    # pivot value can be exchanged with contents of split point
    return (i+1)

In [43]:
arr = [10,7,8,9,1,5]
n=len(arr)
quickSort(arr,0,n-1)
print(arr)


[1, 5, 7, 8, 9, 10]

In [ ]: