Arrays

An array is a linear collection of data values that are accessible at numbered indices, starting at 0. Arrays are stored in continguous memory. There are two types of arrays, static and dynamic. Static arrays are fixed length, meaning they will always take up the same amount of memory.

Dynamic arrays can change in size, and in statically typed languages like C++ there are called vectors. Dynamic arrays allocate double the amount of memory you have specified to account for adding values to it. When you reach a full array, then it allocates a new array with double the size and copies the values over which is an O(n) operation.

Complexity

• Accessing at index: O(1)
• Updating at index: O(1)
• Inserting at beginning: O(n)
• Inserting in middle: O(n)
• Inserting at end: O(1) for dynamic, O(n) for static or reallocating dynamic
• Removing from beginning: O(n)
• Removing from middle: O(n)
• Removing from end: O(1)
• Copying: O(n)
• Traversing (including mapping, filtering, etc): O(n)

Common Algorithms

Binary Search

Binary search is useful when trying to find values in a sorted array. It works by picking a middle point to check, and then dividing the array in half based on whether the value is too big or small.

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1