Basics¶

In [1]:

arr = [12, 10, 92, 3]

Linear Search: O(n)¶

In [2]:

def linearSearch(arr, item):
    return item in arr

In [3]:

print('Linear Search\n\n92: {}\n22: {}'.format(linearSearch(arr, 92), linearSearch(arr, 22)))

Linear Search

92: True
22: False

Binary Search: O(log n)¶

In [4]:

def binarySearch(arr, low, high, item):
    if high < low:
        return -1
    
    mid = int(low + (high - low) / 2)    # Overflow Safe version of (low + high) / 2
    
    if item == arr[mid]:
        return mid
    
    if item > arr[mid]:
        return binarySearch(arr, (mid + 1), high, item)
    
    return binarySearch(arr, low, (mid - 1), item)

In [5]:

sortedArr = arr[:]    # Or list(arr) - Shallow Copy
sortedArr.sort()

print("Index of {} in {}: {}".format(12, sortedArr, binarySearch(sortedArr, 0, len(sortedArr), 12)))

Index of 12 in [3, 10, 12, 92]: 2

Insert Unsorted: O(1)¶

In [6]:

def insertUnsorted(arr, item):
    arr.append(item)
    return arr

In [7]:

print("Before: {}".format(arr))
print("After: {}".format(insertUnsorted(arr, 23)))

Before: [12, 10, 92, 3]
After: [12, 10, 92, 3, 23]

Insert Sorted: O(n)¶

In [8]:

def insertSorted(arr, item):
    i = len(arr) - 1
    
    while i >= 0 and arr[i] > item:
        i -= 1
        
    arr.insert(i + 1, item)

In [9]:

insertSorted(sortedArr, 0)
insertSorted(sortedArr, 15)
insertSorted(sortedArr, 100)
sortedArr

Out[9]:

[0, 3, 10, 12, 15, 92, 100]

Delete Unsorted: O(n)¶

In [10]:

def deleteUnsorted(arr, item):
    arr.remove(item)

In [11]:

deleteUnsorted(arr, 3)
arr

Out[11]:

[12, 10, 92, 23]

Delete Sorted: O(n)¶

In [12]:

def deleteSorted(arr, item):
    i = binarySearch(arr, 0, len(arr), item)
    
    del arr[i]

In [13]:

deleteSorted(sortedArr, 100)
sortedArr

Out[13]:

[0, 3, 10, 12, 15, 92]