Data structures Arrays, Sets

Arrays, Sets

An array is a collection of items indexed by a key.
Sets are unordered lists with no duplicate items.
Linear searching in arrays requires N steps.
The binary search in ordered arrays requires logN steps.

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
"""

 Last update: 224 days ago

minte9 LearnRemember