Programming

  minte9
LearnRemember



Data Structures / Arrays, Sets 

What is an array?
How are sets different from arrays?
How many steps are required to search in an array?
What is the algorithm for searching ordered arrays?

Reading / 1 step

A computer can jump to any memory address in one step. 
 
data = ['apples', 'bananas', 'oranges']

item = data[index] # Reading takes 1 step

print('Found item =', item)
print("Steps =", 1)

"""
    Found item = bananas
    Steps = 1
"""

Searching / N steps

For N cells in an array, linear search would take a maximum of N steps. 
 
def search_value(arr, value):
    steps = 0

    for i in range(len(arr)):
        steps += 1

        if value == arr[i]:
            return i, steps 

    return -1, steps

data = ['apples', 'bananas', 'oranges']
key, steps = search_value(data, 'oranges')

print('Found at index =', key)
print('N =', len(data))
print('Steps =', steps)

"""
    Found at index = 2
    N = 3
    Steps = 3
"""

Insertion / N+1 steps

We need to shift items in order to make room for the new item. 
 
def add_item(data, new_value, key):
    data.append('') # add element at the end of array

    steps = 0
    for i in range(len(data), key+1, -1): # shift the elements to the right
        data[i-1] = data[i-2]
        steps += 1

    print(data)
    data[key] = new_value
    steps += 1
    return steps

data = ['apples', 'bananas', 'oranges']  
print(data)

size = len(data)  
steps = add_item(data, 'cherries', 0)

print(data)
print('N =', size)
print('Steps =', steps)

"""
    ['apples', 'bananas', 'oranges']
    ['apples', 'apples', 'bananas', 'oranges']
    ['cherries', 'apples', 'bananas', 'oranges']
    N = 3
    Steps = 4
"""

Deletion / N+1 steps

To delete an item require one step, then N-1 step for shifting the rest of elements. 
 
def delete_item(data, key):
    steps = 0
    for i in range(key, len(data)-1): # shift elements to left (down to key)
        data[i] = data[i+1]
        steps += 1
    
    data.pop() # remove last element
    steps += 1

    return steps

data = ['apples', 'bananas', 'oranges']  
size = len(data)  
steps = delete_item(data, 0)

print(data)
print('N =', size)
print('Steps =', steps)

"""
    ['bananas', 'oranges']
    N = 3
    Steps = 3
"""

Set / Insertion

A set is a data structure of unordered elements that doesn't allow duplicates. In terms of time compexity, the only difference between arrays and sets is at insertion. 
 
def add_item(data, new_value):
    steps = 0

    # Check for duplicates
    for item in data:
        steps += 1
        if item == new_value:
            return -1

    # Add new value to the set (random location in the set)
    data.add(new_value)
    steps += 1

    return steps


data = {'apples', 'bananas', 'oranges', 'cherries'} 
steps = add_item(data, 'mangos')

print(data)
print('Steps =', steps, '\n')

"""
    {'oranges', 'mangos', 'bananas', 'apples', 'cherries'}
    Steps = 5 
"""

Ordered / Binary Search

When inserting we need to make a search before in order to get the correct spot. While insertion is less efficient for an ordered array, the search is match more efficient. 
 
def binary_seach(arr, val):
    left = 0
    right = len(arr) - 1

    steps = 0
    while True:
        steps += 1

        middle = (left + right) // 2

        if val == arr[middle]:
            return middle, steps

        if val > arr[middle]:
            left = middle + 1

        if val < arr[middle]:
            right = middle - 1

        if left > right:
            return -1, steps

data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
key, steps = binary_seach(data, 7)
print("Found:", key, end=' ')
print("Steps =", steps)

data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
key, steps = binary_seach(data, 17)
print("Found:", key, end=' ')
print("Steps =", steps)

data = [i for i in range(0, 100_100)]
key, steps = binary_seach(data, 70_000)
print("Found:", key, end=' ')
print("Steps =", steps)

"""
    Found: 6 Steps = 4
    Found: 16 Steps = 5
    Found: 70000 Steps = 16
"""




References