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)
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))
Time complexity, time complexity of Binary Search is $T(n) = T(n/2)+c$, above recurrence can be solved using Recurrence, $O(\log{n})$.
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)
In [35]:
alist
Out[35]:
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)
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)
In [ ]: